Bibliographic record and links to related information available from the Library of Congress catalog
Note: Electronic data is machine generated. May be incomplete or contain other coding.

```1   Introduction to the Theory of Computation               1
1.1 Mathematical Preliminaries and Notation . . . . . . . . . . . 3
Sets . .......... ..        .............        3
Functions and Relations. ...  . . . . . . . . . . . .  6
Graphs and  Trees..... .. . .............        8
Proof Techniques ....... .    ............ ..10
1.2 Three Basic Concepts ......           ........      16
Languages ............ .    ............       .. 16
Grammars  ............      .............       20
Automata  ............      . ....   .......    26
1.3 Some Applications* ... ..... .    ............ .30
2   Finite Automata                                        37
2.1  Deterministic Finite Accepters  .. . . . . . . . ... . . . . .  38
Deterministic Accepters and Transition Graphs . . . . . 38
Languages and Dfa's ..... . ...........         40
Regular Languages ....... ..............        44
2.2 Nondeterministic Finite Accepters. . . . . . .... . . . .  49
Definition of a Nondeterministic Accepter . . . . . . . . 49
Why Nondeterminism? ................         . 53
2.3 Equivalence of Deterministic and Nondeterministic Finite
Accepters  . . . . . . . . . . . . . . . . . . . . . . . . . . .  56
2.4 Reduction of the Number of States in Finite Automata*  .  63
3   Regular Languages and Regular Grammars                    71
3.1 Regular Expressions .......................           71
Formal Definition of a Regular Expression. . . . . . . . 72
Languages Associated with Regular Expressions . . . .72
3.2 Connection Between Regular Expressions and Regular
Languages ..............          ..... ... .....   77
Regular Expressions Denote Regular Languages . . . . . 78
Regular Expressions for Regular Languages . . . . . . . 80
Regular Expressions for Describing Simple Patterns . . 86
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 of Regular Languages and Regular
Grammars.......... ....        ......... ..95
4   Properties of Regular Languages                           99
4.1 Closure Properties of Regular Languages . . . . . . . . ... 100
Closure under Simple Set Operations . . . . . . . . ... 100
Closure under Other Operations . . . . . . . . . .  . 102
4.2 Elementary Questions about Regular Languages ...... . .111
4.3 Identifying Nonregular Languages  . . . . . . . . . . . .. 114
Using the Pigeonhole Principle . . . . . . . . . . .  . 114
A Pumping Lemma    .....    .............. 115
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 . . . . . . . . . 140
5.3 Context-Free Grammars and Programming Languages. . .. 146
6   Simplification of Context-Free Grammars and Normal
Forms                                                 149
6.1 Methods for Transforming Grammas . . . . . . . . . .  . 150
A Useful Substitution Rule . ............. . 150
Removing Useless Productions . . . . . . . . . . . . . . 152
Removing A-Productions. . .  . . ... . ...... . . 156
Removing Unit-Productions .  . . . . . . . . . . . . . . 158
6.2 Two Important Normal Forms . .   . . . . . . . . . . . . . . 164
Chomsky Normal Form   . . ..............          164
Greibach Normal Form  . . ..............          167
6.3  A Membership Algorithm for Context-Free Grammars* . . . 171
7   Pushdown Automata                                         175
7.1 Nondeterministic Pushdown Automata . . . . . . . . ... 176
Definition of a Pushdown Automaton . . . . . . ... 176
The Language Accepted by a Pushdown Automaton . . 180
7.2 Pushdown Automata and Context-Free Languages . . . . . . 185
Pushdown Automata for Context-Free Languages . . . .185
Context-Free Grammars for Pushdown Automata . . .190
7.3 Deterministic Pushdown Automata and Deterministic
Context-Free Languages  . . . .  . . . . . . . . . . . . . . 196
7.4  Grammars for Deterministic Context-Free Languages*  . .. 201
8   Properties of Context-Free Languages                      205
8.1 Two Pumping Lemmas ...... ............. 205
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 . . . . . . . . .. . 214
Some Decidable Properties of Context-Free Languages . 218
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.    ............. .......             243
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-Qption . . . . . . . . . . 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 . . . . . . .... . . . 260
10.3 Nondeterministic Turing Machines . . . . . . . . . . . . . . . 262
10.4 A Universal Turing Machine. . . . . . . . . . . .  . .  266
10.5 Linear Bounded Automata . . . . . . . . . . . . . . . . . . . 271
11 A Hierarchy of Formal Languages And Automata             275
11.1 Recursive and Recursively Enumerkble 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 ..... . . . . . . . . . . . . . .  . 282
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 .....................294
12 Limits of Algorithmic Computation                        297
12.1 Some Problems That Cannot Be Solved by Turing
M achines  ...........  ................         . 298
Computability and Decidability . . . . . . . . . . . . . . 298
The Turing Machine Halting Froblem  . . . . . . .  . 299
Reducing One Undecidable Problem to Another . . . . 302
12.2 Undecidable Problems for Recursively Enumerable
Languages ...................         ........ 306
12.3 The Post Correspondence Problem  . . . . . . . . . . . . . . 309
12.4 Undecidable Problems for Context-Free Languages . . .  . .316
12.5 A Question of Efficiency . . . . . . . . . . . . . . .....  . 320
13 Other Models of Computation                              323
13.1 Recursive Functions ...................       .. ..325
Primitive Recursive Functions . . . . . . . . .  .  . . . 326
Ackermann's Function . . . . . . . . . . . . . . . .  . 329
p Recursive Functions . . . . . . . . . . . . . . ...  331
13.2  Post Systems  ............    ..   .. ...........  333
13.3 Rewriting Systems ...................       .....337
Matrix Grammars .............        ......      ..338
Markov  Algorithms . ..................      ...338
L-System s  .  .  .  .  .  .  .  .  .  .  ...... ..........340
14 An Overview of Computational Complexity                  343
14.1  Efficiency of Computation  .. . . . . . . . . . ... . . . . . 344
14.2 Turing Machine Models and Complexity  . . . . . . . . . . . 346
14.3 Language Families and Complexity Classes . . . . . . . . . . 349
14.4 The Complexity Classes P and NP  . . . .   . . . . .  . . . 353
14.5 Some NP Problems . . . . . . . . . ... . .. . . . . .. 354
14.6 Polynomial-Time Reduction . . . . . . . . . . . .  .  . .  358
14.7 NP-Completeness and an Open Question . . . . . . . . . . . 360

```

Library of Congress subject headings for this publication: Formal languages, Machine theory