New to this Edition:
- Expanded and simplified discussions of some of the more
difficult ideas and constructions such as the pumping lemmas,
the “finite automata to regular expression” construction, and
the “Pushdown to context-free grammar” algorithm.
- New examples that clearly illustrate the above concepts.
- An Introduction of transition graphs for pushdown automata
and Turing machines.
- Chapter 14 has been expended, making it suitable for a one
or one and a half week discussion of computational
complexity.
- New and revised exercises throughout.
- Instructor’s guide with solutions manual and instructor’s
website available.
1. Introduction to the Theory of Computation
2. Finite Automata
3. Regular Language and Regular Grammars
4. Properties of Regular languages
5. Context-Free language
6. Simplification of Context-Free Grammars and Normal Forms
7. Pushdown Automata
8. Properties of Context-Free Languages
9. Turning Machines
10. Other Models of Turing Machines
Etc.