This problem set is due on Sunday, 19 February so that we can have it graded and returned to you prior to the first exam. Please email it to Sean and to Lynn. If you produce it on paper, you can email it by using one of the scanning copiers in the Academic Center (or in the Olin Center faculty suites provided that you do it at a time when you have access).

1. Deterministic Finite State Automata

   Draw state diagrams for deterministic finite automata accepting each of the following languages:

   1. aa*
   2. (ab)*(ba)*
   3. { w | w contains at least three 1s } (where w is a string over the alphabet { 0, 1 })
   4. { w | w doesn't contain the substring 110 } (where w is a string over the alphabet { 0, 1 })
   Also give the transition table for problem 1b.
2. Nondeterministic Finite State Automata

   Draw state diagrams for nondeterministic finite automata accepting each of the following languages:

   1. (ab)*(ba)* U aa*
   2. ((ab U aab)* a*)*
   3. ((a*b*a*)* b*)
   Also give the transition table for problem 2c.
3. Relationship between Deterministic and Nondeterministic Finite State Automata
   • Do Sipser problem 1.12 (sorry, there's a picture and pictures don't wikify well....)
4. Proving properties of FSMs Prove that every nondeterministic finite automaton can be converted to an equivalent one that has a single accept state.
5. Pumping Lemma

   Use the pumping lemma to show that the language {0ⁿ 1^m | n <= m } is not regular.

6. (Extra Credit/Challenge Problems): Sipser problem 1.25; Sipser problem 1.37.

NB: These problems are often based on or taken directly from some of the books we're using in this class. Credits available on request.