Enhanced descriptions from Syndetics:

.

Table of contents provided by Syndetics

• Chapter 1 Introduction to the Theory of Computation (p. 1)
• 1.1 Mathematical Preliminaries and Notation (p. 3)
• Sets (p. 3)
• Functions and Relations (p. 5)
• Graphs and Trees (p. 7)
• Proof Techniques (p. 9)
• 1.2 Three Basic Concepts (p. 15)
• Languages (p. 15)
• Grammars (p. 19)
• Automata (p. 25)
• 1.3 Some Applications (p. 29)
• Chapter 2 Finite Automata (p. 35)
• 2.1 Deterministic Finite Accepters (p. 36)
• Deterministic Accepters and Transition Graphs (p. 36)
• Languages and Dfas (p. 38)
• Regular Languages (p. 42)
• 2.2 Nondeterministic Finite Accepters (p. 47)
• Definition of a Nondeterministic Accepter (p. 48)
• Why Nondeterminism? (p. 52)
• 2.3 Equivalence of Deterministic and Nondeterministic Finite Accepters (p. 55)
• 2.4 Reduction of the Number of States in Finite Automata (p. 62)
• Chapter 3 Regular Languages and Regular Grammars (p. 71)
• 3.1 Regular Expressions (p. 71)
• Formal Definition of a Regular Expression (p. 72)
• Languages Associated with Regular Expressions (p. 73)
• 3.2 Connection Between Regular Expressions and Regular Languages (p. 78)
• Regular Expressions Denote Regular Languages (p. 78)
• Regular Expressions for Regular Languages (p. 81)
• Regular Expressions for Describing Simple Patterns (p. 85)
• 3.3 Regular Grammars (p. 89)
• Right- and Left-Linear Grammars (p. 89)
• Right-Linear Grammars Generate Regular Languages (p. 91)
• Right-Linear Grammars for Regular Languages (p. 93)
• Equivalence Between Regular Languages and Regular Grammars (p. 95)
• Chapter 4 Properties of Regular Languages (p. 99)
• 4.1 Closure Properties of Regular Languages (p. 100)
• Closure under Simple Set Operations (p. 100)
• Closure under Other Operations (p. 103)
• 4.2 Elementary Questions about Regular Languages (p. 111)
• 4.3 Identifying Nonregular Languages (p. 114)
• Using the Pigeonhole Principle (p. 114)
• A Pumping Lemma (p. 115)
• Chapter 5 Context-Free Languages (p. 125)
• 5.1 Context-Free Grammars (p. 126)
• Examples of Context-Free Languages (p. 127)
• Leftmost and Rightmost Derivations (p. 129)
• Derivation Trees (p. 130)
• Relation Between Sentential Forms and Derivation Trees (p. 132)
• 5.2 Parsing and Ambiguity (p. 136)
• Parsing and Membership (p. 136)
• Ambiguity in Grammars and Languages (p. 141)
• 5.3 Context-Free Grammars and Programming Languages (p. 146)
• Chapter 6 Simplification of Context-Free Grammars (p. 149)
• 6.1 Methods for Transforming Grammars (p. 150)
• A Useful Substitution Rule (p. 150)
• Removing Useless Productions (p. 152)
• Removing [lambda]-Productions (p. 156)
• Removing Unit-Productions (p. 158)
• 6.2 Two Important Normal Forms (p. 165)
• Chomsky Normal Form (p. 165)
• Greibach Normal Form (p. 168)
• 6.3 A Membership Algorithm for Context-Free Grammars (p. 172)
• Chapter 7 Pushdown Automata (p. 175)
• 7.1 Nondeterministic Pushdown Automata (p. 176)
• Definition of a Pushdown Automaton (p. 176)
• A Language Accepted by a Pushdown Automaton (p. 179)
• 7.2 Pushdown Automata and Context-Free Languages (p. 184)
• Pushdown Automata for Context-Free Languages (p. 184)
• Context-Free Grammars for Pushdown Automata (p. 189)
• 7.3 Deterministic Pushdown Automata and Deterministic Context-Free Languages (p. 195)
• 7.4 Grammars for Deterministic Context-Free Languages (p. 200)
• Chapter 8 Properties of Context-Free Languages (p. 205)
• 8.1 Two Pumping Lemmas (p. 206)
• A Pumping Lemma for Context-Free Languages (p. 206)
• A Pumping Lemma for Linear Languages (p. 210)
• 8.2 Closure Properties and Decision Algorithms for Context-Free Languages (p. 213)
• Closure of Context-Free Languages (p. 213)
• Some Decidable Properties of Context-Free Languages (p. 218)
• Chapter 9 Turing Machines (p. 221)
• 9.1 The Standard Turing Machine (p. 222)
• Definition of a Turing Machine (p. 222)
• Turing Machines as Language Accepters (p. 229)
• Turing Machines as Transducers (p. 232)
• 9.2 Combining Turing Machines for Complicated Tasks (p. 238)
• 9.3 Turing's Thesis (p. 244)
• Chapter 10 Other Models of Turing Machines (p. 249)
• 10.1 Minor Variations on the Turing Machine Theme (p. 250)
• Equivalence of Classes of Automata (p. 250)
• Turing Machines with a Stay-Option (p. 251)
• Turing Machines with Semi-Infinite Tape (p. 253)
• The Off-Line Turing Machine (p. 255)
• 10.2 Turing Machines with More Complex Storage (p. 258)
• Multitape Turing Machines (p. 258)
• Multidimensional Turing Machines (p. 261)
• 10.3 Nondeterministic Turing Machines (p. 263)
• 10.4 A Universal Turing Machine (p. 266)
• 10.5 Linear Bounded Automata (p. 270)
• Chapter 11 A Hierarchy of Formal Languages and Automata (p. 275)
• 11.1 Recursive and Recursively Enumerable Languages (p. 276)
• Languages That Are Not Recursively Enumerable (p. 278)
• A Language That Is Not Recursively Enumerable (p. 279)
• A Language That Is Recursively Enumerable But Not Recursive (p. 281)
• 11.2 Unrestricted Grammars (p. 283)
• 11.3 Context-Sensitive Grammars and Languages (p. 289)
• Context-Sensitive Languages and Linear Bounded Automata (p. 290)
• Relation Between Recursive and Context-Sensitive Languages (p. 292)
• 11.4 The Chomsky Hierarchy (p. 295)
• Chapter 12 Limits of Algorithmic Computation (p. 299)
• 12.1 Some Problems That Cannot Be Solved By Turing Machines (p. 300)
• The Turing Machine Halting Problem (p. 301)
• Reducing One Undecidable Problem to Another (p. 304)
• 12.2 Undecidable Problems for Recursively Enumerable Languages (p. 308)
• 12.3 The Post Correspondence Problem (p. 312)
• 12.4 Undecidable Problems for Context-Free Languages (p. 318)
• Chapter 13 Other Models of Computation (p. 323)
• 13.1 Recursive Functions (p. 325)
• Primitive Recursive Functions (p. 326)
• Ackermann's Function (p. 330)
• 13.2 Post Systems (p. 334)
• 13.3 Rewriting Systems (p. 337)
• Markov Algorithms (p. 339)
• L-Systems (p. 340)
• Chapter 14 An Introduction to Computational Complexity (p. 343)
• 14.1 Efficiency of Computation (p. 344)
• 14.2 Turing Machines and Complexity (p. 346)
• 14.3 Language Families and Complexity Classes (p. 350)
• 14.4 The Complexity Classes P and NP (p. 353)
• Answers to Selected Exercises (p. 357)
• References (p. 405)
• Index (p. 407)