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