PROBLEM SET 1, CSC 280, 2006 DUE BEFORE CLASS, WED. FEB. 1 The first problem set is as follows (I will shortly place this on the course web site as well). All 10 problems will be marked out of the same total. Answers to any 7 questions make a complete answer paper. However, you can do all questions to earn bonus points (i.e., you can in principle obtain "more than 100%" on the assignment. Reminder: The problems are expected to be done by you alone, without direct ~~~~~~~~ outside or collaborative help (but you may certainly discuss the general principles involved with others; and the TAs may sometimes provide help to the class as a whole, in recitations or on the web site, at their discretion); see web site or notes handed out previously for details about collaboration. Keep your eyes on the instructor's and the TAs' web site for any corrections or discussion. PROBLEM 1 ~~~~~~~~~ On pp. 46-7, Sipser sketches a proof that the regular languages are closed under union. (This was also briefly covered in class, though not in the overhead lecture notes.) He indicates that a more formal proof would include an inductive proof that the construction of the "union machine" M really works. Provide such a proof; i.e., for the basis, show that M works correctly for "short" strings, then assume for induction that it works correctly for strings of length k (i.e., such a string will take M to an accepting state iff it takes either M1 or M2 to an accepting state), and prove that it works correctly for strings of length k+1. (Hint: Think of this in terms of the particular state that is reached in M by a particular string of length k, and then think about the conditions under which a particular additional symbol takes M to an accepting or non-accepting state.) PROBLEM 2 ~~~~~~~~~ a. Can we always convert a DFA with multiple accepting states to a DFA with one accepting state? Why or why not? Justify your answer in detail. b. Give the state diagram of a 6-state DFA for the language L of strings over {a,b} where each string consists of 2 a's followed by 0 or more b's, or 2 b's followed by 0 or more a's. (Hint: first construct a state diagram that ignores edges that cannot lead to an accepting state. Then add a single state that all the ignored edges lead to.) c. For the language L in (b), consider L*. Give a BRIEF English (non-symbolic) characterization of this expanded language, and give the state diagram of a DFA recognizing it. (Unnecessarily complex answers will lose marks.) d. A DFA is obviously a special case of an NFA, if one views both kinds of automata in terms of their state graphs (as we commonly do, when not being absolutely formal): a DFA just lacks epsilon-edges and has exactly one edge exiting from each state for each symbol in the assumed alphabet, labeled with that symbol. However, from the perspective of our formal tuple/set-theory based definition of the 2 kinds of automata, no DFA is (strictly) an NFA. State what the differences are that prevent formal identity of any DFA with any NFA. PROBLEM 3 ~~~~~~~~~ Sipser Exercise 1.14. PROBLEM 4 ~~~~~~~~~ Sisper Exercises 1.4(a,c), 1.5(c,e), 1.6(b,d). PROBLEM 5 ~~~~~~~~~ Sipser Exercises 1.7(b,c,e) PROBLEM 6 ~~~~~~~~~ Consider the NFA in example 1.33 in the text (p. 52). Convert this NFA to an equivalent DFA (showing the state diagram), by using the ideas in the proof of Theorem 1.39. PROBLEM 7 ~~~~~~~~~ a. Complete the following statements by supplying a suitable condition on L(R), where R is a regular expression and e is the empty-string symbol: i. L(R U e) = L(R) iff ... ii. L(R ° Ø) = L(R) iff ... Briefly justify your answers. b. Let's call a string that contains at least one a and at least one b an "ab-string". For the languages determined by each of the following regular expressions (where E+ is an abbreviation for EE*), give 2 ab-strings of length at least 4 that are in the language, and 2 ab-strings of length at most 4 that are not in the language (so, 4 strings per language): i. (a(abb)* U b) ii. (a+ U (ab)+) iii. (a U b+)a+b+ c. Give regular expressions for the languages of Sipser Exercise 1.6(b,d,f) PROBLEM 8 ~~~~~~~~~ Sipser Exercise 1.12 PROBLEM 9 ~~~~~~~~~ Convert the regular expression (ab* U ba*)* to an NFA, using the conversion procedure that was the basis of the proof that for any regular expression R there is an NFA N such that L(N) = L(R). Show intermediate stages in the construction. PROBLEM 10 ~~~~~~~~~~ Sipser Problem 1.41