| |

| |

| |

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