CS 254: Automata and Computability

Assignment #4

Hand in any three of these on paper by 8:30AM Monday, May 10.
Hand in the rest by noon, May 13.

This assignment focuses on creating simple context-free grammars, converting CFGs to Greibach and Chomsky normal forms, and using the Pumping Lemma.

1. Do problem 71 from page 334 (Miscellaneous Exercises) of Kozen
2. See my e-mail entitled "the cursed problem set" from 5/10/10.
   Do problem 72 from page 334 (Miscellaneous Exercises) of Kozen
   Do problem 72(a), (d) from page 334. For part (a), do both Greibach and Chomsky normal forms. For (d), do only Chomsky.
3. Do problem 75 from page 335 (Miscellaneous Exercises) of Kozen
4. Do problem 84, parts (a), (b), (f), and (g) from page 336 (Miscellaneous Exercises) of Kozen.
5. Do problem 85, parts (a), (b), (c), and (d) from page 336 (Miscellaneous Exercises) of Kozen.