Homework 4

Out: 30 Nov 2008, Due: 8 Dec 2008

1. Problem 1.64a
2. Exercises 2.1, 2.4(b,c,e,f), 2.8, 2.12, 2.15, 2.17
3. Problem 2.31
   • Hint: consider 1^p0^p0^p1^p
4. Bonus: Problem 2.20
   • Hint: Let P be a pushdown automaton that recognizes A and D be a DFA that recognizes B. A pushdown automaton P' that recognizes A/B consists of essentially two components, one for recognizing the first part w and another that simulates the string x. The harder one to design is the second component. Try to use nondeterminism (e.g., epsilon moves) to simulate P that works with non-existing string x while tracking the states of D.
5. Bonus: 1.60, 1.61