| |
| |
| |
| 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 | |