Homework 5

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.21b. First rip out 1, then 2, and then 3. Make sure you show intermediate steps of the procedure!
2. 1.29b
3. 1.30
4. 1.32 (Use a DFA)
5. 1.49a (Clarification: k can be any value. It is not a fixed value. In other words, if you can find some value k such that you can write it in this form, then a string is in the language. Hint: Describe the language more simply.)
6. 1.49b
7. 1.55g
8. 1.62