| |
| |
| |
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 Dfas | |
| |
| |
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 Between 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 | |
| |
| |
| |
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 | |
| |
| |
A 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 | |
| |
| |
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 | |
| |
| |
| |
Other Models of Computation | |
| |
| |
| |
Recursive Functions | |
| |
| |
Primitive Recursive Functions | |
| |
| |
Ackermann's Function | |
| |
| |
| |
Post Systems | |
| |
| |
| |
Rewriting Systems | |
| |
| |
Markov Algorithms | |
| |
| |
L-Systems | |
| |
| |
| |
An Introduction to Computational Complexity | |
| |
| |
| |
Efficiency of Computation | |
| |
| |
| |
Turing Machines and Complexity | |
| |
| |
| |
Language Families and Complexity Classes | |
| |
| |
| |
The Complexity Classes P and NP | |
| |
| |
Answers to Selected Exercises | |
| |
| |
References | |
| |
| |
Index | |