An Introduction to Formal Languages and Automata [6th ed.]

Description

Contents......Page 3 Preface......Page 8 1 INTRO TO THEORY OF COMPUTATION......Page 11 Sets......Page 13 Functions and Relations......Page 16 Graphs and Trees......Page 18 Proof Techniques......Page 19 Languages......Page 27 Grammars......Page 30 Automata......Page 36 1.3 Some Applications*......Page 40 2 FINITE AUTOMATA......Page 47 2.1 Deterministic Finite Accepters......Page 48 Languages and Dfa’s......Page 51 Regular Languages......Page 56 Definition of a Nondeterministic Accepter......Page 61 Why Nondeterminism?......Page 65 2.3 Equivalence of Deterministic and Nondeterministic Finite Accepters......Page 68 2.4 Reduction of the Number of States in Finite Automata*......Page 76 3 REGULAR LANGUAGES & REGULAR GRAMMARS......Page 83 Formal Definition of a Regular Expression......Page 84 Languages Associated with Regular Expressions......Page 85 Regular Expressions Denote Regular Languages......Page 90 Regular Expressions for Regular Languages......Page 92 Regular Expressions for Describing Simple Patterns......Page 98 3.3 Regular Grammars......Page 101 Right- and Left-Linear Grammars......Page 102 Right-Linear Grammars Generate Regular Languages......Page 103 Right-Linear Grammars for Regular Languages......Page 106 Equivalence of Regular Languages and Regular Grammars......Page 107 4 PROPERTIES OF REGULAR LANGUAGES......Page 111 Closure under Simple Set Operations......Page 112 Closure under Other Operations......Page 115 4.2 Elementary Questions about Regular Languages......Page 124 Using the Pigeonhole Principle......Page 127 A Pumping Lemma......Page 128 5 CONTEXT-free LANGUAGES......Page 139 5.1 Context-Free Grammars......Page 140 Examples of Context-Free Languages......Page 141 Leftmost and Rightmost Derivations......Page 143 Derivation Trees......Page 144 Relation Between Sentential Forms and Derivation Trees......Page 147 5.2 Parsing and Ambiguity......Page 150 Parsing and Membership......Page 151 Ambiguity in Grammars and Languages......Page 155 5.3 Context-Free Grammars and Programming Languages......Page 161 6 SIMPLIFICATION OF CONTEXT-free GRAMMARS & NORMAL FORMS......Page 164 6.1 Methods for Transforming Grammars......Page 165 A Useful Substitution Rule......Page 166 Removing Useless Productions......Page 168 Removing λ-Productions......Page 172 Removing Unit-Productions......Page 174 Chomsky Normal Form......Page 180 Greibach Normal Form......Page 183 6.3 A Membership Algorithm for Context-Free Grammars*......Page 187 7 PUSHDOWN AUTOMATA......Page 190 7.1 Nondeterministic Pushdown Automata......Page 191 Definition of a Pushdown Automaton......Page 192 The Language Accepted by a Pushdown Automaton......Page 195 Pushdown Automata for Context-Free Languages......Page 200 Context-Free Grammars for Pushdown Automata......Page 205 7.3 Deterministic Pushdown Automata and Deterministic Context-Free Languages......Page 212 7.4 Grammars for Deterministic Context-Free Languages*......Page 216 8 PROPERTIES OF CONTEXT-free LANGUAGES......Page 221 A Pumping Lemma for Context-Free Languages......Page 222 A Pumping Lemma for Linear Languages......Page 227 Closure of Context-Free Languages......Page 231 Some Decidable Properties of Context-Free Languages......Page 235 9 TURING MACHINES......Page 239 Definition of a Turing Machine......Page 240 Turing Machines as Language Accepters......Page 247 Turing Machines as Transducers......Page 250 9.2 Combining Turing Machines for Complicated Tasks......Page 257 9.3 Turing’s Thesis......Page 263 10 OTHER MODELS OF TURING MACHINES......Page 267 Equivalence of Classes of Automata......Page 268 Turing Machines with a Stay-Option......Page 269 Turing Machines with Semi-Infinite Tape......Page 271 The Off-Line Turing Machine......Page 273 Multitape Turing Machines......Page 276 Multidimensional Turing Machines......Page 279 10.3 Nondeterministic Turing Machines......Page 281 10.4 A Universal Turing Machine......Page 284 10.5 Linear Bounded Automata......Page 289 11 HIERARCHY OF FORMAL LANGUAGES & AUTOMATA......Page 293 11.1 Recursive and Recursively Enumerable Languages......Page 294 Languages That Are Not Recursively Enumerable......Page 296 A Language That Is Not Recursively Enumerable......Page 297 A Language That Is Recursively Enumerable but Not Recursive......Page 299 11.2 Unrestricted Grammars......Page 301 11.3 Context-Sensitive Grammars and Languages......Page 307 Context-Sensitive Languages and Linear Bounded Automata......Page 308 Relation Between Recursive and Context-Sensitive Languages......Page 310 11.4 The Chomsky Hierarchy......Page 313 12 LIMITS OF ALGORITHMIC COMPUTATION......Page 316 Computability and Decidability......Page 317 The Turing Machine Halting Problem......Page 318 Reducing One Undecidable Problem to Another......Page 322 12.2 Undecidable Problems for Recursively Enumerable Languages......Page 326 12.3 The Post Correspondence Problem......Page 330 12.4 Undecidable Problems for Context-Free Languages......Page 336 12.5 A Question of Efficiency......Page 339 13 OTHER MODELS OF COMPUTATION......Page 342 13.1 Recursive Functions......Page 344 Primitive Recursive Functions......Page 345 Ackermann’s Function......Page 349 μ Recursive Functions......Page 350 13.2 Post Systems......Page 353 Matrix Grammars......Page 357 Markov Algorithms......Page 358 L-Systems......Page 360 14 OVERVIEW OF COMPUTATIONAL COMPLEXITY......Page 362 14.1 Efficiency of Computation......Page 363 14.2 Turing Machine Models and Complexity......Page 365 14.3 Language Families and Complexity Classes......Page 369 14.4 The Complexity Classes P and NP......Page 372 14.5 Some NP Problems......Page 374 14.6 Polynomial-Time Reduction......Page 377 14.7 NP-Completeness and an Open Question......Page 380 A.1 A General Framework......Page 383 A.2 Mealy Machines......Page 384 A.3 Moore Machines......Page 386 A.4 Moore and Mealy Machine Equivalence......Page 388 A.5 Mealy Machine Minimization......Page 392 A.6 Moore Machine Minimization......Page 397 A.7 Limitations of Finite-State Transducers......Page 398 JFLAP Tool......Page 401 Answers......Page 403 Refs......Page 445 Index......Page 446