Chapter 0 Preface¶
Chapter 1 Introduction¶
Chapter 2 Mathematical Background¶
Chapter 3 Finite Acceptors¶
Chapter 4 Regular Languages¶
Chapter 5 Identifying Non-regular Languages¶
Chapter 6 Context-Free Grammars and Languages¶
Chapter 7 Pushdown Automata¶
Chapter 8 Properties of Context-free Languages¶
Chapter 9 Parsing¶
Chapter 10 Models of Computation¶
Chapter 11 Limits to Computing¶
- 11.1. Reductions
- 11.2. NP-Completeness
- 11.3. NP-Completeness Proofs
- 11.4. Formula Satisfiability
- 11.5. 3-CNF Satisfiability
- 11.6. Reduction of SAT to 3-SAT
- 11.7. The Clique Problem
- 11.8. The Independent Set Problem
- 11.9. Reduction of Clique to Independent Set
- 11.10. Reduction of 3-SAT to Clique
- 11.11. Coping with NP-Complete Problems
- 11.12. Recursively Enumerable Languages
- 11.13. Unsolveable Problems
