| |
| |
| |
Automata: The Methods and the Madness | |
| |
| |
| |
Why Study Automata Theory | |
| |
| |
| |
Introduction to Formal Proof | |
| |
| |
| |
Additional Forms of Proof | |
| |
| |
| |
Inductive Proofs | |
| |
| |
| |
The Central Concepts of Automata Theory | |
| |
| |
| |
Summary of Chapter 1 | |
| |
| |
| |
Gradiance Problems for Chapter 1 | |
| |
| |
| |
References for Chapter 1 | |
| |
| |
| |
Finite Automata | |
| |
| |
| |
An Informal Picture of Finite Automata | |
| |
| |
| |
Deterministic Finite Automata | |
| |
| |
| |
Nondeterministic Finite Automata | |
| |
| |
| |
An Application_ Text Search | |
| |
| |
| |
Finite Automata With EpsilonTransitions | |
| |
| |
| |
Summary of Chapter 2 | |
| |
| |
| |
Gradiance Problems for Chapter 2 | |
| |
| |
| |
References for Chapter 2 | |
| |
| |
| |
Regular Expressions and Languages | |
| |
| |
| |
Regular Expressions | |
| |
| |
| |
Finite Automata and Regular Expressions | |
| |
| |
| |
Applications of Regular Expressions | |
| |
| |
| |
Algebraic Laws for Regular Expressions | |
| |
| |
| |
Summary of Chapter 3 | |
| |
| |
| |
Gradiance Problems for Chapter 3 | |
| |
| |
| |
References for Chapter 3 | |
| |
| |
| |
Properties of Regular Languages | |
| |
| |
| |
Proving Languages Not to Be Regular | |
| |
| |
| |
Closure Properties of Regular Languages | |
| |
| |
| |
Decision Properties of Regular Languages | |
| |
| |
| |
Equivalence and Minimization of Automata | |
| |
| |
| |
Summary of Chapter 4 | |
| |
| |
| |
Gradiance Problems for Chapter 4 | |
| |
| |
| |
References for Chapter 4 | |
| |
| |
| |
Context-Free Grammars and Languages | |
| |
| |
| |
Context-Free Grammars | |
| |
| |
| |
Parse Trees | |
| |
| |
| |
Applications of Context-Free Grammars | |
| |
| |
| |
Ambiguity in Grammars and Languages | |
| |
| |
| |
Summary of Chapter 5 | |
| |
| |
| |
Gradiance Problems for Chapter 5 | |
| |
| |
| |
References for Chapter 5 | |
| |
| |
| |
Pushdown Automata | |
| |
| |
| |
Definition of the Pushdown Automaton | |
| |
| |
| |
The Languages of a PDA | |
| |
| |
| |
Equivalence of PDA's and CFG's | |
| |
| |
| |
Deterministic Pushdown Automata | |
| |
| |
| |
Summary of Chapter 6 | |
| |
| |
| |
Gradiance Problems for Chapter 6 | |
| |
| |
| |
References for Chapter 6 | |
| |
| |
| |
Properties of Context-Free Languages | |
| |
| |
| |
Normal Forms for Context-Free Grammars | |
| |
| |
| |
The Pumping Lemma for Context-Free Languages | |
| |
| |
| |
Closure Properties of Context-Free Languages | |
| |
| |
| |
Decision Properties of CFL's | |
| |
| |
| |
Summary of Chapter 7 | |
| |
| |
| |
Gradiance Problems for Chapter 7 | |
| |
| |
| |
References for Chapter 7 | |
| |
| |
| |
Introduction to Turing Machines | |
| |
| |
| |
Problems That Computers Cannot Solve | |
| |
| |
| |
The Turing Machine | |
| |
| |
| |
Programming Techniques for Turing Machines | |
| |
| |
| |
Extensions to the Basic Turing Machine | |
| |
| |
| |
Restricted Turing Machines | |
| |
| |
| |
Turing Machines and Computers | |
| |
| |
| |
Summary of Chapter 8 | |
| |
| |
| |
Gradiance Problems for Chapter 8 | |
| |
| |
| |
References for Chapter 8 | |
| |
| |
| |
Undecidability | |
| |
| |
| |
A Language That Is Not Recursively Enumerable | |
| |
| |
| |
An Undecidable Problem That Is RE | |
| |
| |
| |
Undecidable Problems About Turing Machines | |
| |
| |
| |
Post's Correspondence Problem | |
| |
| |
| |
Other Undecidable Problems | |
| |
| |
| |
Summary of Chapter 9 | |
| |
| |
| |
Gradiance Problems for Chapter 9 | |
| |
| |
| |
References for Chapter 9 | |
| |
| |
| |
Intractable Problems | |
| |
| |
| |
The Classes P and NP | |
| |
| |
| |
An NP-Complete Problem | |
| |
| |
| |
A Restricted Satisfiability Problem | |
| |
| |
| |
Additional NP-Complete Problems | |
| |
| |
| |
Summary of Chapter 10 | |
| |
| |
| |
Gradiance Problems for Chapter 10 | |
| |
| |
| |
References for Chapter 10 | |
| |
| |
| |
Additional Classes of Problems | |
| |
| |
| |
Complements of Languages in NP | |
| |
| |
| |
Problems Solvable in Polynomial Space | |
| |
| |
| |
A Problem That Is Complete for PS | |
| |
| |
| |
Language Classes Based on Randomization | |
| |
| |
| |
The Complexity of Primality Testing | |
| |
| |
| |
Summary of Chapter 11 | |
| |
| |
| |
Gradiance Problems for Chapter 11 | |
| |
| |
| |
References for Chapter 11 | |
| |
| |
Index | |