CS–172 Computability & Complexity, Spring 2009Feb. 26, 2009Some Homework 3 SolutionsNote: These solutions are not necessarily model answers. Rather, they are designed to be tutorial in nature,and sometimes contain a little more explanation than an ideal solution. Also, bear in mind that there maybe more than one correct solution.1. (a) Not regular. Proof by contradiction: assume that L = {w : w has balanced parentheses} is regular.Let n be the constant guaranteed to exist by the pumping lemma. Consider the string w = (n)n— i.e.,n (’s followed by n )’s. Clearly w has balanced parentheses, so w ∈ L. Thus, since |w| ≥ n, by thepumping lemma we must be able to write w = xyz with |xy| ≤ n, |y| ≥ 1, and such that xyiz ∈ Lfor all i ≥ 0. However, since w starts with n (’s, y must consist entirely of one or more (’s. Therefore,for any i > 1, xyiz /∈ L since it has more (’s than )’s. This is a contradiction, so L is not regular.(b) Regular. The key observation here is that successive occurrences of abb and of bba in any string over{a, b} must alternate along the string. To see this, one can show that in any string w, between any twooccurrences of abb there is an occurrence of bba and vice versa. Consider an arbitrary substring of wdelimited by two occurrences of abb. This string has the form abbuabb, where u is a possibly emptystring. If u contains no a symbols, then the string bbua ends in bba. Otherwise, suppose that the first ain u occurs at position i; then the string bbu1. . . uiends in bba. For the other direction, again consideran arbitrary substring of w delimited by two occurrences of bba. Then the reversal wRof w has theform abbuabb for some string u. By the above argument, wRmust contain bba as a substring, so witself contains an occurrence of abb.For a string w, let D (w) denote the difference between the number of occurrences of abb and of bba inw. By the above argument, for any w, |D(w)| ≤ 1. At this point it is not difficult to see what a DFAfor our language should look like. The states should keep track of the last two symbols seen, as wellas the sign of the quantity D(w). (See diagram; the start state is qst, and the accept states are markedin thicker lines.)qstabaa0ab0ba0bb0aa−ab−ba−bb+abababaabbbababaababba1[The key point in this question is to observe that occurrences of abb and bba must alternate along thestring.](e) Not regular. Assume that this language is regular, and let n be any number bigger than both 2 and thepumping length. Consider the string w = anbn; this contains n − 2 copies of aaa and n − 2 copies ofbbb, so it is in the language. By the pumping lemma there exists a split w = xyz such that |xy| ≤ n,y 6= ǫ and xy2z is also in the language. However, whenever x and y satisfy the first two conditions,the string xy2z will be of the form ambn, for some m > n. This string has more copies of aaa thanbbb, so it cannot be in the language. Contradiction.(f) Not regular. We do a proof by contradiction using closure properties. (Note that it apparently isn’tpossible to use the pumping lemma directly here, because we’d have to show that any possible pumpingof a substring y leads to a string that’s not in L, which is hard as L is not very tightly constrained.)So assume L = {0i1j: i, j ≥ 0 and i 6= j} is regular. Since regular languages are closed undercomplementation, the complementL is also regular. Now consider the language L′= {0i1j: i, j ≥0}, which is certainly regular (it is denoted by the regular expression 0∗1∗). Since regular languagesare also closed under intersection, L ∩ L′must also be regular. However, L ∩ L′= {0i1i: i ≥ 0},which we know is not regular (as we saw in class, by the same argument we used to show that the setof 0-1 strings with equal numbers of 0’s and 1’s is not regular). Therefore we have a contradiction, sowe deduce that L itself must not be regular.An alternative argument for this part, using the Myhill-Nerode Theorem, goes as follows. We showthat the relation ∼Lsplits {0, 1}∗into infinitely many equivalence classes, which implies that L is notregular. Indeed, consider the collection of strings C = {0n: n ≥ 0}. We claim that all strings in Care in distinct equivalence classes. For suppose that there exists m 6= n such that 0m∼L0n. Then, bythe definition of ∼L, 0m1n∼L0n1n. But this is impossible since 0m1n∈ L while 0n1n6∈ L.2. (a) Since L is regular, there is a DFA M that accepts it. Modify the DFA in the following way: take alloutgoing edges from all the accepting states (including self-loops) and reroute them to point to a deadstate. We claim that the resulting DFA M′decides min(L). To see this, note that M′certainly cannotaccept any string that is not accepted by M. And a string w is accepted by M′iff the accepting com-putation of M on w does not pass through any intermediate accepting states. But this latter conditioncorresponds precisely to saying that no proper prefix of w is accepted by M, as required.(b) (not *) This language is finite and therefore regular, since every finite language is regular. (To see this,just write down a regular expression that takes the union of the singleton strings.) However, note thatgiven a FA for L we do not in general know how to construct a FA for L10: we know only that such anFA exists. Thus, unlike parts (a) and (c) of this problem, this proof is not constructive.(d) (coming)4 (b) False. E.g., let Σ = {0, 1}, L = {0n1n: n ≥ 0}, and L′= {0m1n: m 6= n}. Then L and L′are bothnon-regular. However L1∩ L2= ∅, which is regular.(c) False. For a counterexample, let L be any non-regular language (e.g., L = {0i1i: i ≥ 0}). Thenwe can write L =S∞i=1Li, where each Liconsists just of the ith string in L in lexicographic order.Clearly each Liis finite and hence regular. However, the union of all of the Liis L, which is