CS172 Computability & Complexity, Spring 2009Homework 2Out: 5 Feb, 2009Due: 12 Feb., 2009Note: Not all questions are of equal difficulty. Questions marked with an asterisk (*) are to be handed in. The othersare for practice and will not be graded. Put your solutions to the (*) problems in the homework box on Soda level 2by 4pm on the due date. Take time to write clear and concise answers; confused and long-winded solutions will bepenalized. You are allowed to work in small groups to discuss the homework and gain an understanding of what’sinvolved, but your submitted solutions must be completely your own work. Depending on grading resources, we mightonly grade a random subset of the required problems and simply check off the rest; so you are advised to attempt allquestions.1. (*) An all-paths NFA is defined in the same way as a standard NFA, except the definition of acceptanceis changed so that the machine accepts a string w if and only if all possible computations on input wlead to accepting states. (In other words, if any computation on w dies out or ends in a rejecting state,the machine rejects; else it accepts.) Show that the class of languages accepted by an all-paths NFAis exactly the class of regular languages. [HINT: One direction is obvious. For the other, think aboutthe construction we used to convert an NFA into a DFA.]2. Show that regular languages are closed under reverse. The reverse of language L is LR= {wR: w∈L}, where (w1· · · wn)R= wnwn−1· · · w1.Show they are also closed under intersection; i.e., that L1∩L2= {w: w ∈ L1and w ∈ L2} is regularif L1and L2are.3. (*) Show that regular languages are closed under shuffle: for languages L1and L2over Σ, their shuffleis the language = {w: w = a1b1· · · akbk, a1· · · ak∈ L1, b1· · · bk∈ L2and each ai, bi∈ Σ∗}.4. Construct regular expressions that denote each of the following languages:(a) The set of all words over the English alphabet that have “kk” as a substring. [NOTE: Use thesymbol Σ as shorthand for the regular expression a ∪b ∪ . . . ∪ z, denoting the English alphabet.](b) (*) The set of all words over the English alphabet that begin with a vowel (i.e., with ‘a’, ‘e’, ‘i’,‘o’ or ‘u’) and end in ‘ing’.(c) The set of all words over the English alphabet that have at least two k’s.(d) (*) The set of all 0-1 strings in which the number of 1’s is divisible by three.(e) The set of all words over the English alphabet that have an even number of vowels and threeconsonants.(f) (*) The set of all 0-1 strings such that in any prefix, there is at most one more 1 than 0’s and atmost one more 0 than 1’s. (x is a prefix of w∈ L if w = xy and |y| ≥ 1.(g) The set of all words over the English alphabet that have a vowel in every odd position.5. (*) Let R, S be arbitrary regular expressions. Which of the following statements are true? If thestatement is true, give a proof; if it is false, give a counterexample.(a) (R ∪ S)∗≡ R∗∪ S∗; (b) (R∗)∗≡ R∗; (c) if R∗≡ S∗then R ≡ S.NOTE: The symbol ‘≡’ denotes equivalence of regular expressions: R ≡ S means that L(R) = L(S)(R and S denote the same language).6. In the text, the construction of an NFA for the regular expression R∗from an NFA for R involvesadding a new start state q′0with an ǫ-transition to the old start state q0(and also ǫ-transitions from allaccepting states to q0). Since the new NFA must accept the empty string, we make q′0an acceptingstate. Suppose we didn’t add q′0, but instead just made the old start state q0accepting (and added theother ǫ-transitions into q0as before). Give a small example which shows that this simpler constructiondoes not always work