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 | |
Table of Contents provided by Publisher. All Rights Reserved. |