SOLUTIONS TO PRACTICE PROBLEMS P 301 1 (a) Not regular. Use homomorphism h(a)=0 & h(b)=11 (b) Not regular. Proof : (By contradiction) Assume it is accepeted by a DFA with "n" states. Let x=a^(n*n) . Length of x is n*n & hence is clearly in the language. Therefore x=uvw for some u,v,w with 0< |v| <= n. By pumping lemma, uvvw is in the language. Length of uvvw = length of uvw + length of v <= n*n + n < (n+1)^2. Hence length of uvvw is strictly between 2 consecutive squares n^2 and (n+1)^2. Hence cannot be a square. Hence our assumption that language is regular is false. P 315 2 (a) state a b ->(1,1) (2,1) (2,2) (2,1) (1,1) (1,2) (2,2) (1,2) (1,1) (1,2) (2,2) (2,1) for union {(2,1),(2,2),(1,2)} are the final states for intersection {(2,2)} is the final state P 316 3 (a) abbbb (b) state a b ->{s} {s,t,u,v} {d} {s,t,u,v} {s,t,u,v} {s,t,u} {s,t,u} {s,t,u,v} {s,t} {s,t} {s,t,u,v} {s} {d} {d} {d} All states except {d} are final states {d} is a **DEAD STATE** P 316 4 (a) state a b ->{s} {s,t} {d} {s,t} {s,t} {s,t} {d} {d} {d} {{s},{s,t}} are final states {d} is a **DEAD STATE** (b) (a + ab*b)* P 319 11 (a) b* (b) a* + b+a* (it is "b+" concatenated by "a*") P 320 13 (a)-(iii) (b)-(iv) (c)-(i) (d)-(ii) (e)-(v) P 320 15 ((a+b)a)*(a+b)b)* P 321 18 (i) (0+1)*, 0* + 1* No, consider x = 01, which is in the first but not the second. (ii) 0(120)*12, 01(201)*2 Yes, since (120)*1 = 1(201)* (see formula 9.14, p.50). (iii) N*, e* (where N is the null set) Yes. The null set starred is {e} (set with just empty string), and so is {e}*... this was HW1. (iv) (0*1*)*, (0*1)* No. Consider x = 0. It's in the first but not the second. (v) (01 + 0)*0, 0(10 + 0)* Yes. (01 + 0)*0 = (0(1 + e))*0 = 0((1 + e)0)* by 9.14, p.50 = 0(10 + 0)* P 321 19 (a) This is simply b*a*, as shown in class. (b) The string in complement either doesn't contain substring ab, or contains a c: b*a* + (a+b+c)*c(a+b+c)* Can be also done by constructing a DFA, flipping final and non-final states and simplifying. You do MUCH more work and get something like (a + b)*(e + aa* + (c + aa*(c + b(a+b)*c))(a+b+c)*) P 324 35,36: Solutions in book. P 325 41 A is an infinite subset, so given any k > 0, we can choose a^nb^n from A such that n > k. Proceed with the normal proof that {a^nb^n} is not regular. P 322 28 Given a regular language A, show that A' = {xy | x1y is in A} is also regular. Let M be a DFA accepting A. Let M = (Q, E, d, s, F). (E = Sigma, the alphabet, d = transition function.) We will construct an NFA M' = (Q', E, d', s', F') that accepts A'. First, make another copy of Q, and call it Q_1. That is, for each q in Q, there is a corresponding q_1 in Q_1, but we have the provision that q is not equal to q_1. So Q_1 is disjoint from Q. The states of M' will be Q' = Q U Q_1 (U = union). s' = s (the same start state as M). The transition function is described as follows. Note d' is a map from (Q U Q_1) x E to (Q U Q_1). For each transition in M of the form d(q, 0) = q', we have the corresponding transitions in M': d'(q, 0) = q' and d'(q_1, 0) = q'_1 so no real change happens here: the original and the copy do the same thing. The interesting case is when d(q, 1) = q'. Here, we shall have: d'(q, 1) = q', d'(q_1, 1) = q'_1, AND (the crucial one) d'(q, e) = q'_1, where e = the empty string. Finally, F' = {q_1 in Q_1 | q is in F}; that is, the elements of Q_1 whose corresponding elements in Q are final states in M. Why does this work? I'll give an intuitive explanation here. I can prove it formally on request. We begin in the original set of states of M, and behave just like M for a while. At some point (after reading x), our M' nondeterministically switches from working within Q to working in Q_1, via the epsilon transition. When it does this, it also "skips" a 1 that M would have read; the original M would have read a 1 and moved to the next state, but M' moves to the next state but does not read any symbol. Then after some string y has been read, M' stops on some state in Q_1. Note that an e-transition must be taken at some point in the computation in order for M' to accept, and it can only be taken once (going from Q to Q_1). P 325 37 (g) Not regular. Proof by contradiction. Let "k" be the number of states in the DFA accepting the given language. Consider x=a^kb^(k+481) which is in the language. Then "v" consists of only "a"s . Hence the "uw" has more than 481 "b"s than "a"s . But by pumping lemma uw belongs to the language , a contradiction. (alternate proof) Call the language A. Suppose A is regular. Then B = { a^481} A is regular, since concatenation preserves regularity. Language C = { a^nb^n | n<481} is finite, thus regular. B + C is exactly {a^n b^n | n >=0 } which is not regular. (h) Not regular. Proof by contradiction. Let "k" be the number of states in the DFA accepting the given language. Consider x=a^(k+481)b^k which is in the language. Then "v" consists of only "a"s . Hence by pumping "v" , the number of "a"s increase. This implies that the difference between number of "a"s and "b"s is no longer bounder by 481, a contradiction . (i) Regular Easy to build an automaton with 481 * 2 + 3 states accepting the language (l) Not regular Proof by contradiction. Let "k" be the number of states in the DFA accepting the given language. Consider x=a^kb^kc^k which is in the language. Then "v" consists of only "a"s . Hence the "uw" has fewer "a"s than "b"s & "c"s. But by pumping lemma uw belongs to the language , a contradiction. (alternate proof) Use homomorphism h(a) = a, h(b) = b, h(c) = epsilon. You'll get language {a^n b^n | n>=0 } P 326 45 (a) Without loss of generality assume that A does not contain the empty string. The language A can be written as A = { a^i | i is in set S } for some subset of natural numbers S. Let 0 < n_1 < n_2 < n_3 < ... be the members of S in increasing order. Let d_i be the greatest common divisor of numbers n_1, n_2, ..., n_i. Clearly d_{i+1} is less or equal to d_i for every i. Thus there is a limit d = lim d_i as i approaches infinity. Onthe other hand, since all d_i are integers, there has to be some k such that d = d_k. We call d to be the GCD of the set S. We claim that (i) No word whose length is not divisible by d is in A^*. Easy to see, because concatenation of words of length divisible by d has length divisible by d. (ii) Every word of the form a^{nd} such that nd >= n_1 * n_2 * ... * n_k is in A^* Proof is by induction on k. (i) and (ii) together give the claim.