CS172 Computability & Complexity, Spring 2009Homework 4Out: 19 Feb, 2009Due: 26 Feb., 2009Note: Questions marked with an asterisk (*) are to be handed in. The others are for practice and will not be graded.Put your solutions to the (*) problems in the (now unique) homework box on Soda level 2 by 4pm on the due date. Theusual remarks about clear answers and the collaboration policy still hold. Depending on grading resources, we maygrade only a random subset of the problems and check off the rest; so you are advised to attempt all questions.1. This problem consists of four parts, three of which are designed to improve your understanding of theMyhill-Nerode Theorem and the DFA minimization algorithm.(a) (*) Recall the following DFA M , which we saw in Homework 1:q q1010q 0,1210Determine the equivalence relation RMfor this DFA. You should specify the equivalence rela-tion by writing down each of its equivalence classes in the form of a regular expression. [NOTES:(i) Recall that the relation RMis defined by xRMy iff M ends up in the same state on inputs xand y. (ii) Recall also from HW1 that you have already described the set of strings that take Mto each of its states.](b) (*) In class we showed that if L is a regular language, then the equivalence relation RL(indis-tinguishability) has only finitely many equivalence classes (these correspond to the states of theminimal DFA for L). Now consider the language L = {0n1n: n ≥ 0}. By describing theequivalence classes of RL, prove that L is not regular. [NOTES: (i) Recall that the relation RLisdefined by xRLy iff ∀z(xz ∈ L ⇔ yz ∈ L). Of course, we could also prove that L is not regularusing the pumping lemma; the point of this problem is to get you to use a different method basedon the Myhill-Nerode Theorem.](c) Now use the pumping lemma to show that L is not regular.(d) (*) Apply the minimization procedure discussed in class to construct a minimal DFA that isequivalent to the following DFA. Show clearly the steps you used to arrive at your answer; youshould consider the pairs of states in lexicographic order.BCDFGA10000001111E102. Consider the language L = {w = aibjck: i, j, k ≥ 0 and if i = 1 then j = k}.(a) Show that L “acts like” a regular language with respect to the pumping lemma. Specifically,give a pumping length p and show that L satisfies the conditions of the lemma for this p.(b) Now show that L is NOT regular.(c) Why is this not a contradiction?3. (*) Show that for any positive integer n there is a language Lnfor which both of the followingstatements hold(a) There is a DFA with n states that recognizes Lnand(b) No DFA with fewer than n states recognizes Ln.4. The pumping lemma says that every regular language L has a pumping length p, and that any stringw= w1w2· · · wn∈ L with n ≥ p can be pumped. Clearly if p is a pumping length for L, so is p′with p′≥ p. The minimum pumping length for L is the smallest p that is a pumping length for L.[e.g., when L = 01∗, the minimum pumping length is 2: the string w= 0 is in L, has length 1, butcannot be pumped (why?), but any string in L of length ≥ 2 must contain a 1 and can be pumped(why?, how?)].For each of the following languages, find the minimum pumping length and justify your answer.(a) L = 0001∗(b) (*) L = 1011(c) L = 0∗1∗(d) (*) L = 001 ∪ 0∗1∗(e) (*) L = 10(11∗0)0(f) L = 0∗1∗0∗1∗∪ 10∗1(g) (*) L = (01)∗(h) (*) L = ε(i) (*) L =