A printable PDF is available.

Assignment 2: Due Thursday, September 18

1. Design a DFA that works over the alphabet Sigma={0,1,2,3,4,5,6,7,8,9} and accepts strings that give decimal numbers that are divisible by 3. Give both a diagram illustrating your DFA and a formal description.
2. Textbook, page 84, Exercise 1.6 a-b.
3. The proof of Theorem 1.25 in the book (stating that the class of regular languages is closed under union) started by defining a combined DFA, but then it wasn't proved formally that the new DFA accepts the correct language. Sipser says "its correctness is evident from the strategy described in the proof idea." This is true, but it's also good practice to understand the structure of such proofs by doing simple examples, so that's what you are to do for this exercise: write out the formal induction proof that the defined DFA accepts A₁ union A₂.
4. Textbook, page 86, Exercise 1.21.
5. Textbook, page 90, Problem 1.46, parts a and c.
6. Textbook, page 128, Exercise 2.1.
7. Textbook, page 128, Exercise 2.2.
8. Textbook, page 129, Exercise 2.14.
9. Textbook, page 130, Problem 2.20.
10. Textbook, page 131, Problem 2.30 a.