Introduction to automata theory, languages, and computation

Preface iii......Page 3
Table of Contents vii......Page 7
1 Automata: The Methods and the Madness 1......Page 15
1.1.1 Introduction to Finite Automata 2......Page 16
1.1.2 Structural Representations 4......Page 18
1.2 Introduction to Formal Proof 5......Page 19
1.2.1 Deductive Proofs 6......Page 20
1.2.2 Reduction to Definitions 8......Page 22
1.2.3 Other Theorem Forms 10......Page 24
1.3 Additional Forms of Proof 13......Page 27
1.3.2 The Contrapositive 14......Page 28
1.3.3 Proof by Contradiction 16......Page 30
1.3.4 Counterexamples 17......Page 31
1.4.1 Inductions on Integers 19......Page 33
1.4.2 More General Forms of Integer Inductions 22......Page 36
1.4.3 Structural Inductions 23......Page 37
1.4.4 Mutual Inductions 26......Page 40
1.5.1 Alphabets 28......Page 42
1.5.2 Strings 29......Page 43
1.5.3 Languages 30......Page 44
1.5.4 Problems 31......Page 45
1.6 Summary of Chapter 1 34......Page 48
1.7 References for Chapter 1 35......Page 49
2 Finite Automata 37......Page 51
2.1.1 The Ground Rules 38......Page 52
2.1.2 The Protocol 39......Page 53
2.1.3 Enabling the Automata to Ignore Actions 41......Page 55
2.1.4 The Entire System as an Automaton 43......Page 57
2.2 Deterministic Finite Automata 45......Page 59
2.2.2 How a DFA Processes Strings 46......Page 60
2.2.3 Simpler Notations for DFA\'s 48......Page 62
2.2.4 Extending the Transition Function to Strings 49......Page 63
2.2.5 The Language of a DFA 52......Page 66
2.2.6 Exercises for Section 2.2 53......Page 67
2.3 Nondeterministic Finite Automata 55......Page 69
2.3.1 An Informal View of Nondeterministic Finite Automata 56......Page 70
2.3.2 Definition of Nondeterministic Finite Automata 57......Page 71
2.3.3 The Extended Transition Function 58......Page 72
2.3.4 The Language of an NFA 59......Page 73
2.3.5 Equivalence of Deterministic and Nondeterministic Finite Automata 60......Page 74
2.3.6 A Bad Case for the Subset Construction 65......Page 79
2.3.7 Exercises for Section 2.3 66......Page 80
2.4.1 Finding Strings in Text 68......Page 82
2.4.2 Nondeterministic Finite Automata for Text Search 69......Page 83
2.4.3 A DFA to Recognize a Set of Keywords 70......Page 84
2.5.1 Uses of ε-Transitions 72......Page 86
2.5.2 The Formal Notation for an ε-NFA 74......Page 88
2.5.3 Epsilon-Closures 75......Page 89
2.5.4 Extended Transitions and Languages for ε-NFA\'s 76......Page 90
2.5.5 Eliminating ε-Transitions 77......Page 91
2.6 Summary of Chapter 2 80......Page 94
2.7 References for Chapter 2 81......Page 95
3.1 Regular Expressions 83......Page 97
3.1.1 The Operators of Regular Expressions 84......Page 98
3.1.2 Building Regular Expressions 85......Page 99
3.1.3 Precedence of Regular-Expression Operators 88......Page 102
3.1.4 Exercises for Section 3.1 89......Page 103
3.2 Finite Automata and Regular Expressions 90......Page 104
3.2.1 From DFA\'s to Regular Expressions 91......Page 105
3.2.2 Converting DFA\'s to Regular Expressions by Eliminating States 96......Page 110
3.2.3 Converting Regular Expressions to Automata 101......Page 115
3.2.4 Exercises for Section 3.2 106......Page 120
3.3.1 Regular Expressions in UNIX 108......Page 122
3.3.2 Lexical Analysis 109......Page 123
3.3.3 Finding Patterns in Text 111......Page 125
3.3.4 Exercises for Section 3.3 113......Page 127
3.4.1 Associativity and Commutativity 114......Page 128
3.4.3 Distributive Laws 115......Page 129
3.4.4 The Idempotent Law 116......Page 130
3.4.6 Discovering Laws for Regular Expressions 117......Page 131
3.4.7 The Test for a Regular-Expression Algebraic Law 119......Page 133
3.4.8 Exercises for Section 3.4 120......Page 134
3.6 References for Chapter 3 122......Page 136
4 Properties of Regular Languages 125......Page 139
4.1.1 The Pumping Lemma for Regular Languages 126......Page 140
4.1.2 Applications of the Pumping Lemma 127......Page 141
4.1.3 Exercises for Section 4.1 129......Page 143
4.2.1 Closure of Regular Languages Under Boolean Operations 131......Page 145
4.2.2 Reversal 137......Page 151
4.2.3 Homomorphisms 139......Page 153
4.2.4 Inverse Homomorphisms 140......Page 154
4.2.5 Exercises for Section 4.2 145......Page 159
4.3.1 Converting Among Representations 149......Page 163
4.3.2 Testing Emptiness of Regular Languages 151......Page 165
4.3.4 Exercises for Section 4.3 153......Page 167
4.4.1 Testing Equivalence of States 154......Page 168
4.4.2 Testing Equivalence of Regular Languages 157......Page 171
4.4.3 Minimization of DFA\'s 159......Page 173
4.4.4 Why the Minimized DFA Can\'t Be Beaten 162......Page 176
4.4.5 Exercises for Section 4.4 164......Page 178
4.5 Summary of Chapter 4 165......Page 179
4.6 References for Chapter 4 166......Page 180
5.1 Context-Free Grammars 169......Page 183
5.1.1 An Informal Example 170......Page 184
5.1.2 Definition of Context-Free Grammars 171......Page 185
5.1.3 Derivations Using a Grammar 173......Page 187
5.1.4 Leftmost and Rightmost Derivations 175......Page 189
5.1.5 The Language of a Grammar 177......Page 191
5.1.6 Sentential Forms 178......Page 192
5.1.7 Exercises for Section 5.1 179......Page 193
5.2.1 Constructing Parse Trees 181......Page 195
5.2.2 The Yield of a Parse Tree 183......Page 197
5.2.3 Inference, Derivations, and Parse Trees 184......Page 198
5.2.4 Prom Inferences to Trees 185......Page 199
5.2.5 From Trees to Derivations 187......Page 201
5.2.6 From Derivations to Recursive Inferences 190......Page 204
5.3 Applications of Context-Free Grammars 191......Page 205
5.3.1 Parsers 192......Page 206
5.3.2 The YACC Parser-Generator 194......Page 208
5.3.3 Markup Languages 196......Page 210
5.3.4 XML and Document-Type Definitions 198......Page 212
5.3.5 Exercises for Section 5.3 204......Page 218
5.4.1 Ambiguous Grammars 205......Page 219
5.4.2 Removing Ambiguity From Grammars 207......Page 221
5.4.3 Leftmost Derivations as a Way to Express Ambiguity 211......Page 225
5.4.4 Inherent Ambiguity 212......Page 226
5.4.5 Exercises for Section 5.4 214......Page 228
5.5 Summary of Chapter 5 215......Page 229
5.6 References for Chapter 5 216......Page 230
6.1.1 Informal Introduction 219......Page 233
6.1.2 The Formal Definition of Pushdown Automata 221......Page 235
6.1.3 A Graphical Notation for PDA\'s 223......Page 237
6.1.4 Instantaneous Descriptions of a PDA 224......Page 238
6.1.5 Exercises for Section 6.1 228......Page 242
6.2.1 Acceptance by Final State 229......Page 243
6.2.2 Acceptance by Empty Stack 230......Page 244
6.2.3 From Empty Stack to Final State 231......Page 245
6.2.4 From Final State to Empty Stack 234......Page 248
6.2.5 Exercises for Section 6.2 236......Page 250
6.3.1 From Grammars to Pushdown Automata 237......Page 251
6.3.2 From PDA\'s to Grammars 241......Page 255
6.3.3 Exercises for Section 6.3 245......Page 259
6.4 Deterministic Pushdown Automata 246......Page 260
6.4.2 Regular Languages and Deterministic PDA\'s 247......Page 261
6.4.4 DPDA\'s and Ambiguous Grammars 249......Page 263
6.4.5 Exercises for Section 6.4 251......Page 265
6.5 Summary of Chapter 6 252......Page 266
6.6 References for Chapter 6 253......Page 267
7.1 Normal Forms for Context-Free Grammars 255......Page 269
7.1.1 Eliminating Useless Symbols 256......Page 270
7.1.2 Computing the Generating and Reachable Symbols 258......Page 272
7.1.3 Eliminating ε-Productions 259......Page 273
7.1.4 Eliminating Unit Productions 262......Page 276
7.1.5 Chomsky Normal Form 266......Page 280
7.1.6 Exercises for Section 7.1 269......Page 283
7.2.1 The Size of Parse Trees 274......Page 288
7.2.2 Statement of the Pumping Lemma 275......Page 289
7.2.3 Applications of the Pumping Lemma for CFL\'s 276......Page 290
7.2.4 Exercises for Section 7.2 280......Page 294
7.3 Closure Properties of Context-Free Languages 281......Page 295
7.3.1 Substitutions 282......Page 296
7.3.2 Applications of the Substitution Theorem 284......Page 298
7.3.4 Intersection With a Regular Language 285......Page 299
7.3.5 Inverse Homomorphism 289......Page 303
7.3.6 Exercises for Section 7.3 291......Page 305
7.4 Decision Properties of CFL\'s 293......Page 307
7.4.1 Complexity of Converting Among CFG\'s and PDA\'s 294......Page 308
7.4.2 Running Time of Conversion to Chomsky Normal Form 295......Page 309
7.4.3 Testing Emptiness of CFL\'s 296......Page 310
7.4.4 Testing Membership in a CFL 298......Page 312
7.4.6 Exercises for Section 7.4 302......Page 316
7.5 Summary of Chapter 7 303......Page 317
7.6 References for Chapter 7 304......Page 318
8.1 Problems That Computers Cannot Solve 307......Page 321
8.1.1 Programs that Print \"Hello, World\" 308......Page 322
8.1.2 The Hypothetical \"Hello, World\" Tester 310......Page 324
8.1.3 Reducing One Problem to Another 313......Page 327
8.2 The Turing Machine 316......Page 330
8.2.1 The Quest to Decide All Mathematical Questions 317......Page 331
8.2.2 Notation for the Turing Machine 318......Page 332
8.2.3 Instantaneous Descriptions for Turing Machines 320......Page 334
8.2.4 Transition Diagrams for Taring Machines 323......Page 337
8.2.5 The Language of a Hiring Machine 326......Page 340
8.2.6 Turing Machines and Halting 327......Page 341
8.2.7 Exercises for Section 8.2 328......Page 342
8.3 Programming Techniques for Turing Machines 329......Page 343
8.3.1 Storage in the State 330......Page 344
8.3.2 Multiple Tracks 331......Page 345
8.3.3 Subroutines 333......Page 347
8.3.4 Exercises for Section 8.3 334......Page 348
8.4.1 Multitape Turing Machines 336......Page 350
8.4.2 Equivalence of One-Tape and Multitape TM\'s 337......Page 351
8.4.3 Running Time and the Many-Tapes-to-One Construction 339......Page 353
8.4.4 Nondeterministic Turing Machines 340......Page 354
8.4.5 Exercises for Section 8.4 342......Page 356
8.5.1 Turing Machines With Semi-infinite Tapes 345......Page 359
8.5.2 Multistack Machines 348......Page 362
8.5.3 Counter Machines 351......Page 365
8.5.4 The Power of Counter Machines 352......Page 366
8.5.5 Exercises for Section 8.5 354......Page 368
8.6.1 Simulating a Turing Machine by Computer 355......Page 369
8.6.2 Simulating a Computer by a Turing Machine 356......Page 370
8.6.3 Comparing the Running Times of Computers and Turing Machines 361......Page 375
8.7 Summary of Chapter 8 363......Page 377
8.8 References for Chapter 8 365......Page 379
9 Undecidability 367......Page 381
9.1 A Language That Is Not Recursively Enumerable 368......Page 382
9.1.2 Codes for Turing Machines 369......Page 383
9.1.3 The Diagonalization Language 370......Page 384
9.1.5 Exercises for Section 9.1 372......Page 386
9.2.1 Recursive Languages 373......Page 387
9.2.2 Complements of Recursive and RE languages 374......Page 388
9.2.3 The Universal Language 377......Page 391
9.2.4 Undecidability of the Universal Language 379......Page 393
9.2.5 Exercises for Section 9.2 381......Page 395
9.3.1 Reductions 383......Page 397
9.3.2 Turing Machines That Accept the Empty Language 384......Page 398
9.3.3 Rice\'s Theorem and Properties of the RE Languages 387......Page 401
9.3.5 Exercises for Section 9.3 390......Page 404
9.4.1 Definition of Post\'s Correspondence Problem 392......Page 406
9.4.2 The \"Modified\" PCP 394......Page 408
9.4.3 Completion of the Proof of PCP Undecidability 397......Page 411
9.5.1 Problems About Programs 403......Page 417
9.5.2 Undecidability of Ambiguity for CFG\'s 404......Page 418
9.5.3 The Complement of a List Language 406......Page 420
9.5.4 Exercises for Section 9.5 409......Page 423
9.6 Summary of Chapter 9 410......Page 424
9.7 References for Chapter 9 411......Page 425
10 Intractable Problems 413......Page 427
10.1.2 An Example: Kruskal\'s Algorithm 414......Page 428
10.1.4 An NP Example: The Traveling Salesman Problem 419......Page 433
10.1.5 Polynomial-Time Reductions 421......Page 435
10.1.6 NP-Complete Problems 422......Page 436
10.1.7 Exercises for Section 10.1 423......Page 437
10.2.1 The Satisfiability Problem 426......Page 440
10.2.2 Representing SAT Instances 427......Page 441
10.2.3 NP-Completeness of the SAT Problem 428......Page 442
10.2.4 Exercises for Section 10.2 434......Page 448
10.3 A Restricted Satisfiability Problem 435......Page 449
10.3.1 Normal Forms for Boolean Expressions 436......Page 450
10.3.2 Converting Expressions to CNF 437......Page 451
10.3.3 NP-Completeness of CSAT 440......Page 454
10.3.4 NP-Completeness of 3SAT 445......Page 459
10.3.5 Exercises for Section 10.3 446......Page 460
10.4.1 Describing NP-complete Problems 447......Page 461
10.4.2 The Problem of Independent Sets 448......Page 462
10.4.3 The Node-Cover Problem 452......Page 466
10.4.4 The Directed Hamilton-Circuit Problem 453......Page 467
10.4.5 Undirected Hamilton Circuits and the TSP 460......Page 474
10.4.6 Summary of NP-Complete Problems 461......Page 475
10.4.7 Exercises for Section 10.4 462......Page 476
10.5 Summary of Chapter 10 466......Page 480
10.6 References for Chapter 10 467......Page 481
11 Additional Classes of Problems 469......Page 483
11.1.1 The Class of Languages Co-NP 470......Page 484
11.1.2 NP-Complete Problems and Co-NP 471......Page 485
11.1.3 Exercises for Section 11.1 472......Page 486
11.2.1 Polynomial-Space Turing Machines 473......Page 487
11.2.2 Relationship of PS and NPS to Previously Defined Classes 474......Page 488
11.2.3 Deterministic and Nondeterministic Polynomial Space 476......Page 490
11.3.1 PS-Completeness 478......Page 492
11.3.2 Quantified Boolean Formulas 479......Page 493
11.3.3 Evaluating Quantified Boolean Formulas 480......Page 494
11.3.4 PS-Completeness of the QBF Problem 482......Page 496
11.4 Language Classes Based on Randomization 487......Page 501
11.4.1 Quicksort: an Example of a Randomized Algorithm 488......Page 502
11.4.2 A Turing-Machine Model Using Randomization 489......Page 503
11.4.3 The Language of a Randomized Turing Machine 490......Page 504
11.4.4 The Class RP 492......Page 506
11.4.5 Recognizing Languages in RP 494......Page 508
11.4.6 The Class ZPP 495......Page 509
11.4.7 Relationship Between RP and ZPP 496......Page 510
11.4.8 Relationships to the Classes P and NP 497......Page 511
11.5 The Complexity of Primality Testing 498......Page 512
11.5.1 The Importance of Testing Primality 499......Page 513
11.5.2 Introduction to Modular Arithmetic 501......Page 515
11.5.3 The Complexity of Modular-Arithmetic Computations 503......Page 517
11.5.4 Random-Polynomial Primality Testing 504......Page 518
11.5.5 Nondeterministic Primality Tests 505......Page 519
11.6 Summary of Chapter 11 508......Page 522
11.7 References for Chapter 11 510......Page 524
Index 513......Page 527