CS–172 Computability & Complexity, Spring 2009Feb. 19, 2009Homework 2 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 First, we observe that any DFA is an all-paths NFA, so all-paths NFAs accept all regular languages.For the other direction, we need to show that any language accepted by an all-paths NFA is regular.Let N = (Q, Σ, δ, q0, F ) be an arbitrary all-paths NFA. We will construct a standard NFA M =(Q′, Σ, δ′, q′0, F′) that recognizes the same language as N . The construction will be similar to theconversion from NFAs to DFAs discussed in class (and in Theorem 1.19 of Sipser). The resulting NFAM will be almost a DFA, in that there will be at most one possible path in each computation. However,unlike in a DFA, every time we see a “dying” computation in N, the corresponding computation in Mwill die as well. (Note that this is where our construction differs from the NFA-to-DFA construction!)Q′= P(Q)q′0= {q0}δ′(R, a) =(∅ if for some r ∈ R, δ(r, a) = ∅;{q ∈ Q | q ∈ E(δ(r, a)) for some r ∈ R} otherwise.(Recall that E(R) is the set of states reachable from R using zero or more ǫ transitions.) Finally, wewant M to be accepting if its final state contains only accepting states of N, so we define F′= P(F ).An alternative argument is the following: First, augment the all-paths NFA N into an all-paths NFAN1such that N1accepts the same language as N , but no computation of N1dies. (One way to do thisis to add a rejecting state qdieto N ; then for all states q ∈ Q ∪ {qdie}, add a transition from q to qdielabeled by all symbols in Σ unused by other outgoing arrows at q.) Now, reverse the accepting andrejecting states of N1; call the resulting machine N2. Think of N2as a standard NFA: The languageaccepted by N2is then the complement of the language L accepted by the all-paths NFA N1. Itfollows that the complement of L is regular. Since regular languages are closed under complement(see Problem 3 of Homework 1), L must be regular as well.3 (Coming)4 For each of these, there are many possible valid regular expressions.(b)a ∪ e ∪ i ∪ o ∪ uΣ∗∪ ǫing(d) 0∗10∗10∗10∗∗(f) (10 ∪ 01)∗(1 ∪ 0 ∪ ǫ)To see the above, first notice that every even length string that belongs in the language is suchthat every prefix of it has equally many zeros and ones, because if not, then there are either twomore zeros than ones or two more ones than zeros. It is easy to check, by induction on the lengthof the string, that the set of all even length strings where every prefix has the same number ofzeros and ones is given by (10 ∪ 01)∗. To then get our language, we simply concatenate eithera zero or a one or nothing to the end of every even length string with the above property.5 (a) False. E.g., take R = 0 and S = 1. Then the string 010 belongs to (R ∪ S)∗but not to R∗∪ S∗.[Note that, when the answer is ‘False’, the only convincing way to justify it is by giving a concretecounterexample (like the one above). More general, woolly arguments don’t work. The sameapplies to part (c) below.](b) True. The fact that L(R∗) ⊆ L(R∗)∗is immediate because the language on the right containsall words that consist of finite sequences of words from L(R∗), so in particular it contains allwords in L(R∗). We also have to show that L(R∗)∗⊆ L (R∗). To see this, note that any wordin L(R∗)∗can be written in the form w1w2. . . wnfor some n ≥ 0, where each wiis a wordin L(R∗). But each wican in turn be written in the form xi1xi2. . . ximifor some mi≥ 0, whereeach xijis a word in L(R). So any word in L(R∗)∗can be written as a sequence of wordsfrom L(R), and hence belongs to L(R∗). Thus L(R∗)∗⊆ L (R∗), as claimed.[You could try for some kind of informal argument for this part, e.g., based on conversion toNFAs. The above scheme is really the only convincing way to go here: note that we’re just tryingto show that two sets are equal, so we have to show each is contained in the other. ](c) False. E.g., take R = 0 and S = 0 ∪ ǫ. Then L(R∗) = L(S∗) = {0}∗, but L(R ) = {0} andL(S) = {0,