This classic book on formal languages, automata theory, and computational complexity has been updated to present theoretical concepts in a concise and straightforward manner with the increase of hands-on, practical applications. This new edition comes with Gradiance, an online assessment tool developed for computer science.

1. Automata: The Methods and the Madness

2. Finite Automata

3. Regular Expressions and Languages

4. Properties of Regular Languages

5. Context Free Grammars and Languages

6. Pushdown Automata

7. Properties of Context Free Languages

8. Introduction to Turing Machines

9. Undecidability

10. Intractable Problems

11. Additional Classes of Problems