The homework problems are from Chapter 4 of our text `Introduction to the Theory of Computation' (3rd Edition), by Michael Sipser.
  1. Exercise 4.3 (6 points)
  2. Exercise 4.4 (6 points)
  3. Exercise 4.8 (6 points)
  4. Exercise 4.9 (6 points)
  5. Exercise 4.11 (6 points)
  6. Exercise 4.16 (6 points)
  7. Exercise 4.28 (7 points)
  8. Exercise 4.29 (7 points)

The homework is due in class on Tuesday, November 25.