Automata: The Methods and the Madness / Chapter 1: |
Why Study Automata Theory / 1.1: |
Introduction to Formal Proof / 1.2: |
Additional Forms of Proof / 1.3: |
Inductive Proofs / 1.4: |
The Central Concepts of Automata Theory / 1.5: |
Summary of Chapter 1 / 1.6: |
Gradiance Problems for Chapter 1 / 1.7: |
References for Chapter 1 / 1.8: |
Finite Automata / Chapter 2: |
An Informal Picture of Finite Automata / 2.1: |
Deterministic Finite Automata / 2.2: |
Nondeterministic Finite Automata / 2.3: |
An Application_ Text Search / 2.4: |
Finite Automata With EpsilonTransitions / 2.5: |
Summary of Chapter 2 / 2.6: |
Gradiance Problems for Chapter 2 / 2.7: |
References for Chapter 2 / 2.8: |
Regular Expressions and Languages / Chapter 3: |
Regular Expressions / 3.1: |
Finite Automata and Regular Expressions / 3.2: |
Applications of Regular Expressions / 3.3: |
Algebraic Laws for Regular Expressions / 3.4: |
Summary of Chapter 3 / 3.5: |
Gradiance Problems for Chapter 3 / 3.6: |
References for Chapter 3 / 3.7: |
Properties of Regular Languages / Chapter 4: |
Proving Languages Not to Be Regular / 4.1: |
Closure Properties of Regular Languages / 4.2: |
Decision Properties of Regular Languages / 4.3: |
Equivalence and Minimization of Automata / 4.4: |
Summary of Chapter 4 / 4.5: |
Gradiance Problems for Chapter 4 / 4.6: |
References for Chapter 4 / 4.7: |
Context-Free Grammars and Languages / Chapter 5: |
Context-Free Grammars / 5.1: |
Parse Trees / 5.2: |
Applications of Context-Free Grammars / 5.3: |
Ambiguity in Grammars and Languages / 5.4: |
Summary of Chapter 5 / 5.5: |
Gradiance Problems for Chapter 5 / 5.6: |
References for Chapter 5 / 5.7: |
Pushdown Automata / Chapter 6: |
Definition of the Pushdown Automaton / 6.1: |
The Languages of a PDA / 6.2: |
Equivalence of PDA's and CFG's / 6.3: |
Deterministic Pushdown Automata / 6.4: |
Summary of Chapter 6 / 6.5: |
Gradiance Problems for Chapter 6 / 6.6: |
References for Chapter 6 / 6.7: |
Properties of Context-Free Languages / Chapter 7: |
Normal Forms for Context-Free Grammars / 7.1: |
The Pumping Lemma for Context-Free Languages / 7.2: |
Closure Properties of Context-Free Languages / 7.3: |
Decision Properties of CFL's / 7.4: |
Summary of Chapter 7 / 7.5: |
Gradiance Problems for Chapter 7 / 7.6: |
References for Chapter 7 / 7.7: |
Introduction to Turing Machines / Chapter 8: |
Problems That Computers Cannot Solve / 8.1: |
The Turing Machine / 8.2: |
Programming Techniques for Turing Machines / 8.3: |
Extensions to the Basic Turing Machine / 8.4: |
Restricted Turing Machines / 8.5: |
Turing Machines and Computers / 8.6: |
Summary of Chapter 8 / 8.7: |
Gradiance Problems for Chapter 8 / 8.8: |
References for Chapter 8 / 8.9: |
Undecidability / Chapter 9: |
A Language That Is Not Recursively Enumerable / 9.1: |
An Undecidable Problem That Is RE / 9.2: |
Undecidable Problems About Turing Machines / 9.3: |
Post's Correspondence Problem / 9.4: |
Other Undecidable Problems / 9.5: |
Summary of Chapter 9 / 9.6: |
Gradiance Problems for Chapter 9 / 9.7: |
References for Chapter 9 / 9.8: |
Intractable Problems / Chapter 10: |
The Classes P and NP / 10.1: |
An NP-Complete Problem / 10.2: |
A Restricted Satisfiability Problem / 10.3: |
Additional NP-Complete Problems / 10.4: |
Summary of Chapter 10 / 10.5: |
Gradiance Problems for Chapter 10 / 10.6: |
References for Chapter 10 / 10.7: |
Additional Classes of Problems / Chapter 11: |
Complements of Languages in NP / 11.1: |
Problems Solvable in Polynomial Space / 11.2: |
A Problem That Is Complete for PS / 11.3: |
Language Classes Based on Randomization / 11.4: |
The Complexity of Primality Testing / 11.5: |
Summary of Chapter 11 / 11.6: |
Gradiance Problems for Chapter 11 / 11.7: |
References for Chapter 11 / 11.8: |
Index |
Automata: The Methods and the Madness / Chapter 1: |
Why Study Automata Theory / 1.1: |
Introduction to Formal Proof / 1.2: |
Additional Forms of Proof / 1.3: |
Inductive Proofs / 1.4: |
The Central Concepts of Automata Theory / 1.5: |