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