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 1p0p0p1p
  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