COT3100 Summer’2001Recitation on Languages and Machines07/19/20011. Let A, B and C be sets of strings. Prove or disprove that A(B C) = ABAC.Only one subset relation can be proved, namely we can prove that ABAC A(B C).It actually means that ABAC is “smaller” then A(B C), because there might be a string that belongs to both AB and AC, although it can not be represented as some prefix from A and a suffix that belong to both B and C. So, here is a counterexample that disproves A(B C) ABAC.A={a, ab}, B={b}, C={}. B C={b}, A(B C)={ab, abb}, AB={ab, abb}, AC={a,ab}, and ABAC= {abb}. So, abA(B C), but ab ABAC, so it’s not the case, that always A(B C) ABAC.2. Let A, B and C be sets of strings. Prove or disprove that if A B, then A* B*. Assume A B. To prove A* B*, take some string w A* to show that wB*. By definition of Kleene A* = A0A1A2, w A* means that w An , where n is some integer,n0. w An implies that w = u1u2…un, where ui A for i =1, 2, … n. Since A B, ui A implies that ui B and then w = u1u2…un Bn. By Kleene star definition Bn B*, so that w Bn implies w B*.3. Consider two languages represented by regular expressions: L1= (abc*)* and L2 = (ab+c*)*. Prove or disprove that L1 = L2We can disprove that L1 = L2 if we find a string which belongs to one of languages and does not belong to the other. Strings in L1 consist in some number of repetition pf the pattern abc*, i.e. some number of substrings starting with ab and followed by some number of c’s (this number may be 0). In other words, any sequence of c’s must be preceded by ab. For example, ababccabccccabc L1. Strings in L2 consist from any number of substrings ab and c* in any order. In particular, they may start with some number of c’s, i.e. cc L2, but cc L1.4. Consider the following DFA. 10312aa abbba) Give a sequence of configurations of the DFA for the input string w=aabbbba.(q0, aabbbba) (q0, abbbba) (q0, bbbba) (q1, bbba) (q2, bba) (q2, ba) (q2, a) (q3, ) b) Is w accepted by the DFA?No, because q3 is not an accepting state. c) Give a regular expression of strings accepted by the DFA.a*bbb*5. Construct a DFA to recognize the language represented by the regular expression (a+b)*abb over the alphabet ={a, b}. Give the diagram and transition table. a bq0q1q0q1q1q2q2q1q3q3q1q02a,
View Full Document
Unlocking...