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).

- Deterministic Finite State Automata
Draw state diagrams for

**deterministic**finite automata accepting each of the following languages:- aa*
- (ab)*(ba)*
- { w | w contains at least three 1s } (where w is a string over the alphabet { 0, 1 })
- { w | w doesn't contain the substring 110 } (where w is a string over the alphabet { 0, 1 })

- Nondeterministic Finite State Automata
Draw state diagrams for

**nondeterministic**finite automata accepting each of the following languages:- (ab)*(ba)* U aa*
- ((ab U aab)* a*)*
- ((a*b*a*)* b*)

- Relationship between Deterministic and Nondeterministic Finite State Automata
- Do Sipser problem 1.12 (sorry, there's a picture and pictures don't wikify well....)

- Proving properties of FSMs Prove that every nondeterministic finite automaton can be converted to an equivalent one that has a single accept state.
- Pumping Lemma
Use the pumping lemma to show that the language {0

^{n}1^{m}| n <= m } is not regular. - (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.