A printable PDF is available.

## Assignment 2: Due Thursday, September 18

- 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. - Textbook, page 84, Exercise 1.6 a-b.
- 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*._{1}union A_{2} - Textbook, page 86, Exercise 1.21.
- Textbook, page 90, Problem 1.46, parts a and c.
- Textbook, page 128, Exercise 2.1.
- Textbook, page 128, Exercise 2.2.
- Textbook, page 129, Exercise 2.14.
- Textbook, page 130, Problem 2.20.
- Textbook, page 131, Problem 2.30 a.