Homework 3

General Comments

• Problems are taken from the textbook unless otherwise noted.
• For full credit, provide context for each problem, show all calculations, and explain your work/answers.
• Numbers and/or algebra by themselves are not enough.
• You will lose a significant amount of credit if you do not show enough work/context for your answers.
• Precision is very important. You cannot skip steps, make guesses, or use flawed logic. Any of these things can lead to incorrect answers.
• Homework assignments must be very neatly written or typeset (e.g. using Word or OpenOffice).
• You must indicate any assistance you had on an assignment as specified on the Policies page.

Details

1. 1.7e
2. 1.7g
3. 1.8b
4. 1.9b
5. 1.10b
6. 1.16b (Show the intermediate automata)
7. 1.32

Further details

• For several of the problems, remember that the empty set and the empty string are not the same thing.
• For 1.8b, 1.9b, and 1.10b, you may use NFAs for the initial languages. Please provide the NFAs/DFAs for the initial language(s) and then show the combined one unsimplified. Then simplify if you wish.
• For 1.32 providing a DFA/NFA is a proof (see results in the chapter that imply this). I prefer a state diagram for this problem since it is usually much easier to follow than a formal definition or table.