| |
| |
| |
| Introduction to the Theory of Computation | |
| |
| |
| |
| Mathematical Preliminaries and Notation | |
| |
| |
| Sets | |
| |
| |
| Functions and Relations | |
| |
| |
| Graphs and Trees | |
| |
| |
| Proof Techniques | |
| |
| |
| |
| Three Basic Concepts | |
| |
| |
| Languages | |
| |
| |
| Grammars | |
| |
| |
| Automata | |
| |
| |
| |
| Some Applications | |
| |
| |
| |
| Finite Automata | |
| |
| |
| |
| Deterministic Finite Accepters | |
| |
| |
| Deterministic Accepters and Transition Graphs | |
| |
| |
| Languages and Dfa's | |
| |
| |
| Regular Languages | |
| |
| |
| |
| Nondeterministic Finite Accepters | |
| |
| |
| Definition of a Nondeterministic Accepter | |
| |
| |
| Why Nondeterminism? | |
| |
| |
| |
| Equivalence of Deterministic and Nondeterministic Finite Accepters | |
| |
| |
| |
| Reduction of the Number of States in Finite Automata | |
| |
| |
| |
| Regular Languages and Regular Grammars | |
| |
| |
| |
| Regular Expressions | |
| |
| |
| Formal Definition of a Regular Expression | |
| |
| |
| Languages Associated with Regular Expressions | |
| |
| |
| |
| Connection Between Regular Expressions and Regular Languages | |
| |
| |
| Regular Expressions Denote Regular Languages | |
| |
| |
| Regular Expressions for Regular Languages | |
| |
| |
| Regular Expressions for Describing Simple Patterns | |
| |
| |
| |
| Regular Grammars | |
| |
| |
| Right- and Left-Linear Grammars | |
| |
| |
| Right-Linear Grammars Generate Regular Languages | |
| |
| |
| Right-Linear Grammars for Regular Languages | |
| |
| |
| Equivalence of Regular Languages and Regular Grammars | |
| |
| |
| |
| Properties of Regular Languages | |
| |
| |
| |
| Closure Properties of Regular Languages | |
| |
| |
| Closure under Simple Set Operations | |
| |
| |
| Closure under Other Operations | |
| |
| |
| |
| Elementary Questions about Regular Languages | |
| |
| |
| |
| Identifying Nonregular Languages | |
| |
| |
| Using the Pigeonhole Principle | |
| |
| |
| A Pumping Lemma | |
| |
| |
| |
| Context-Free Languages | |
| |
| |
| |
| Context-Free Grammars | |
| |
| |
| Examples of Context-Free Languages | |
| |
| |
| Leftmost and Rightmost Derivations | |
| |
| |
| Derivation Trees | |
| |
| |
| Relation between Sentential Forms and Derivation Trees | |
| |
| |
| |
| Parsing and Ambiguity | |
| |
| |
| Parsing and Membership | |
| |
| |
| Ambiguity in Grammars and Languages | |
| |
| |
| |
| Context-Free Grammars and Programming Languages | |
| |
| |
| |
| Simplification of Context-Free Grammars and Normal Forms | |
| |
| |
| |
| Methods for Transforming Grammars | |
| |
| |
| A Useful Substitution Rule | |
| |
| |
| Removing Useless Productions | |
| |
| |
| Removing [lambda]-Productions | |
| |
| |
| Removing Unit-Productions | |
| |
| |
| |
| Two Important Normal Forms | |
| |
| |
| Chomsky Normal Form | |
| |
| |
| Greibach Normal Form | |
| |
| |
| |
| A Membership Algorithm for Context-Free Grammars | |
| |
| |
| |
| Pushdown Automata | |
| |
| |
| |
| Nondeterministic Pushdown Automata | |
| |
| |
| Definition of a Pushdown Automaton | |
| |
| |
| The Language Accepted by a Pushdown Automaton | |
| |
| |
| |
| Pushdown Automata and Context-Free Languages | |
| |
| |
| Pushdown Automata for Context-Free Languages | |
| |
| |
| Context-Free Grammars for Pushdown Automata | |
| |
| |
| |
| Deterministic Pushdown Automata and Deterministic Context-Free Languages | |
| |
| |
| |
| Grammars for Deterministic Context-Free Languages | |
| |
| |
| |
| Properties of Context-Free Languages | |
| |
| |
| |
| Two Pumping Lemmas | |
| |
| |
| A Pumping Lemma for Context-Free Languages | |
| |
| |
| A Pumping Lemma for Linear Languages | |
| |
| |
| |
| Closure Properties and Decision Algorithms for Context-Free Languages | |
| |
| |
| Closure of Context-Free Languages | |
| |
| |
| Some Decidable Properties of Context-Free Languages | |
| |
| |
| |
| Turing Machines | |
| |
| |
| |
| The Standard Turing Machine | |
| |
| |
| Definition of a Turing Machine | |
| |
| |
| Turing Machines as Language Accepters | |
| |
| |
| Turing Machines as Transducers | |
| |
| |
| |
| Combining Turing Machines for Complicated Tasks | |
| |
| |
| |
| Turing's Thesis | |
| |
| |
| |
| Other Models of Turing Machines | |
| |
| |
| |
| Minor Variations on the Turing Machine Theme | |
| |
| |
| Equivalence of Classes of Automata | |
| |
| |
| Turing Machines with a Stay-Option | |
| |
| |
| Turing Machines with Semi-Infinite Tape | |
| |
| |
| The Off-Line Turing Machine | |
| |
| |
| |
| Turing Machines with More Complex Storage | |
| |
| |
| Multitape Turing Machines | |
| |
| |
| Multidimensional Turing Machines | |
| |
| |
| |
| Nondeterministic Turing Machines | |
| |
| |
| |
| A Universal Turing Machine | |
| |
| |
| |
| Linear Bounded Automata | |
| |
| |
| |
| A Hierarchy of Formal Languages and Automata | |
| |
| |
| |
| Recursive and Recursively Enumerable Languages | |
| |
| |
| Languages That Are Not Recursively Enumerable | |
| |
| |
| A Language That Is Not Recursively Enumerable | |
| |
| |
| A Language That Is Recursively Enumerable but Not Recursive | |
| |
| |
| |
| Unrestricted Grammars | |
| |
| |
| |
| Context-Sensitive Grammars and Languages | |
| |
| |
| Context-Sensitive Languages and Linear Bounded Automata | |
| |
| |
| Relation Between Recursive and Context-Sensitive Languages | |
| |
| |
| |
| The Chomsky Hierarchy | |
| |
| |
| |
| Limits of Algorithmic Computation | |
| |
| |
| |
| Some Problems That Cannot Be Solved by Turing Machines | |
| |
| |
| Computability and Decidability | |
| |
| |
| The Turing Machine Halting Problem | |
| |
| |
| Reducing One Undecidable Problem to Another | |
| |
| |
| |
| Undecidable Problems for Recursively Enumerable Languages | |
| |
| |
| |
| The Post Correspondence Problem | |
| |
| |
| |
| Undecidable Problems for Context-Free Languages | |
| |
| |
| |
| A Question of Efficiency | |
| |
| |
| |
| Other Models of Computation | |
| |
| |
| |
| Recursive Functions | |
| |
| |
| Primitive Recursive Functions | |
| |
| |
| Ackermann's Function | |
| |
| |
| [micro] Recursive Functions | |
| |
| |
| |
| Post Systems | |
| |
| |
| |
| Rewriting Systems | |
| |
| |
| Matrix Grammars | |
| |
| |
| Markov Algorithms | |
| |
| |
| L-Systems | |
| |
| |
| |
| An Overview of Computational Complexity | |
| |
| |
| |
| Efficiency of Computation | |
| |
| |
| |
| Turing Machine Models and Complexity | |
| |
| |
| |
| Language Families and Complexity Classes | |
| |
| |
| |
| The Complexity Classes P and NP | |
| |
| |
| |
| Some NP Problems | |
| |
| |
| |
| Polynomial-Time Reduction | |
| |
| |
| |
| NP-Completeness and an Open Question | |
| |
| |
| Answers | |
| |
| |
| References | |
| |
| |
| Index | |