Computer Science 313
Theory of Computation
Assignment 2 – Chapter 1 (continued)

Due Monday 14 September

Exercises 1.7bcd, 1.10, and 1.15, and Problems 1.31, 1.32

Hint on Exercise 1.7: look at the solved problems (marked A) in the back of the chapter.

Extra Credit

  • Problem 1.34
  • If you did the DFA programming project in the previous assignment (and even if you didn’t), modify your code to create an NFA class that supports the additional transitions of an NFA. For extra-extra credit, your NFA class could have a buildDFA method that uses the Subset Construction to build a DFA object from an NFA object.