Introduction to Automata Theory, Formal Languages and Computation

Cover......Page 1
Contents......Page 8
Foreword......Page 18
Preface......Page 20
Acknowledgements......Page 22
About the Author......Page 24
 1.1 Basics of String......Page 26
  1.2.2 Finite and Infinite Set......Page 27
  1.2.5 Properties Related to Basic Operation......Page 28
 1.3 Relation on Set......Page 29
  1.4.1 Graph......Page 31
  1.4.7 Tree......Page 32
 1.5 Basics of Digital Electronics......Page 33
 1.6 Digital Circuit......Page 34
 1.8 History of Automata Theory......Page 40
  What We Have Learned So Far......Page 41
  Solved Problems......Page 42
  Fill in the Blanks......Page 44
  Exercise......Page 45
 2.1 Grammar......Page 46
 2.2 The Chomsky Hierarchy......Page 58
  What We Have Learned So Far......Page 61
  Solved Problems......Page 62
  Multiple Choice Questions......Page 65
  GATE Questions......Page 66
  Fill in the Blanks......Page 70
  Exercise......Page 71
 Introduction......Page 72
 3.3 Characteristics of Automaton......Page 73
 3.4 Finite Automata......Page 74
 3.5 Graphical and Tabular Representation of FA......Page 75
 3.6 Transitional System......Page 76
  3.6.1 Acceptance of a String by Finite Automata......Page 77
 3.7 DFA and NFA......Page 78
  3.8.1 Process of Converting an NFA to a DFA......Page 80
 3.9 NFA with e (null) Move......Page 84
  3.9.1 Usefulness of NFA with E Move......Page 85
  3.9.2 Conversion of an NFA with e Moves to DFA without e Move......Page 86
 3.10 Equivalence of DFA and NFA......Page 89
 3.11 Dead State......Page 90
   3.12.3.1 Tabular......Page 91
   3.12.3.2 Transitional......Page 92
 3.13 Conversion of One Machine to Another......Page 95
  3.13.1 Tabular Format......Page 96
  3.13.2 Transitional Format......Page 101
 3.14 Minimization of Finite Automata......Page 106
  3.14.1 Process of Minimizing......Page 107
  3.15.1 Equivalence Relation......Page 110
  3.15.3 Myhill–Nerode Theorem in Minimizing a DFA......Page 111
 3.16 Two-way Finite Automata......Page 116
 3.17 Applications of Finite Automata......Page 117
  Solved Problems......Page 118
  Multiple Choice Questions......Page 144
  GATE Questions......Page 145
  Fill in the Blanks......Page 151
  Exercise......Page 152
 4.1 Sequence Detector......Page 158
 4.2 Binary Counter......Page 163
  4.2.1 Designing Using Flip Flop (T Flip Flop and SR Flip Flop)......Page 164
  4.3.1 Capabilities and Limitations of Finite-State Machine......Page 168
 4.4 State Equivalence and Minimization of Machine......Page 169
 4.5 Incompletely Specified Machine, Minimal Machine......Page 174
  4.5.1 Simplification......Page 175
 4.6 Merger Graph......Page 178
  4.7.3 Compatibility Graph......Page 181
  4.7.5 Minimal Machine......Page 182
  4.8.1 Construction of a Merger Table......Page 184
  4.9.1 Finite Memory Machine......Page 187
  4.9.3 Vanishing of Connection Matrix......Page 188
  4.9.4 Definite Memory Machine......Page 194
 4.10 Information Lossless Machine......Page 198
 4.10.1 Test for Information Losslessness......Page 200
 4.11 Inverse Machine......Page 205
 4.12 Minimal Inverse Machine......Page 206
  What We Have Learned So Far......Page 209
  Solved Problems......Page 210
  Multiple Choice Questions......Page 240
  Fill in the Blanks......Page 242
  Exercise......Page 243
  5.1.1 Some Formal Recursive Definitions of RE......Page 248
  5.2.1 Kleene’s Closure......Page 249
 5.3 Identities of Regular Expression......Page 251
 5.4 The Arden’s Theorem......Page 253
  5.4.1 Process of Constructing Regular Expression from Finite Automata......Page 254
  5.5.1 Conversion of an RE to NFA with e transition......Page 258
  5.5.2 Direct Conversion of RE to DFA......Page 266
 5.6 NFA with e Move and Conversion to DFA by e-Closure Method......Page 269
  5.6.1 Conversion of an NFA with e move to a DFA......Page 270
 5.7 Equivalence of Two Finite Automata......Page 274
 5.8 Equivalence of Two Regular Expressions......Page 277
 5.9 Construction of Regular Grammar from an RE......Page 280
 5.10 Constructing FA from Regular Grammar......Page 283
 5.11 Pumping Lemma for Regular Expression......Page 285
 5.12 Closure Properties of Regular Set......Page 291
 5.13 Decision Problems of Regular Expression......Page 294
 5.14 ‘Grep’ and Regular Expression......Page 295
  What We Have Learned So Far......Page 296
  Solved Problems......Page 297
  Multiple Choice Questions......Page 313
  GATE Questions......Page 314
  Fill in the Blanks......Page 319
  Exercise......Page 320
  6.1.1 Backus Naur Form (BNF)......Page 322
  6.2.1 Derivation......Page 326
  6.2.2 Parse Tree......Page 327
 6.3 Ambiguity in Context-free Grammar......Page 329
  6.4.1 Left Recursion......Page 334
  6.4.2 Left Factoring......Page 337
  6.5.1 Removal of Useless Symbols......Page 338
  6.5.2 Removal of Unit Productions......Page 340
  6.5.3 Removal of Null Productions......Page 343
 6.6 Linear Grammar......Page 346
  6.6.2 Left Linear to Right Linear......Page 347
 6.7 Normal Form......Page 349
  6.7.1 Chomsky Normal Form......Page 350
  6.7.2 Greibach Normal Form......Page 354
  6.8.1 Closed Under Union......Page 358
  6.8.5 Not Closed Under Complementation......Page 359
 6.9 Pumping Lemma for CFL......Page 360
  6.11.1 Emptiness......Page 363
  6.11.2 Finiteness......Page 365
  6.11.3 Membership Problem......Page 366
 6.12 CFG and Regular Language......Page 368
 6.13 Applications of Context-free Grammar......Page 369
  What We Have Learned So Far......Page 370
  Solved Problems......Page 371
  Multiple Choice Questions......Page 393
  GATE Questions......Page 394
  Fill in the Blanks......Page 398
  Exercise......Page 399
  7.1.1 Definition......Page 402
  7.1.2 Mechanical Diagram of the PDA......Page 403
  7.2.2 Accepted by the Final State......Page 404
  7.3.2 Non-deterministic Pushdown Automata (NPDA)......Page 420
 7.4 Construction of PDA from CFG......Page 423
 7.5 Construction of CFG Equivalent to PDA......Page 428
 7.6 Graphical Notation for PDA......Page 431
 7.7 Two-stack PDA......Page 432
  What We Have Learned So Far......Page 433
  Solved Problems......Page 434
  GATE Questions......Page 450
  Fill in the Blanks......Page 452
  Exercise......Page 453
  8.1.1 Mechanical Diagram......Page 454
  8.1.2 Instantaneous Description (ID) in Respect of TM......Page 455
 8.2 Transitional Representation of Turing Machine......Page 470
 8.4 Conversion of Regular Expression to Turing Machine......Page 471
 8.5 Two-stack PDA and Turing Machine......Page 474
  8.5.1 Minsky Theorem......Page 475
  Solved Problems......Page 476
  Multiple Choice Questions......Page 484
  GATE Questions......Page 485
  Fill in the Blanks......Page 487
  Exercise......Page 488
  9.1.1 Multi-tape Turing Machine......Page 489
  9.1.2 Multi-head Turing Machine......Page 494
  9.1.4 K-dimensional Turing Machine......Page 497
  9.1.5 Non-deterministic Turing Machine......Page 498
 9.2 Turing Machine as an Integer Function......Page 500
 9.4 Linear-Bounded Automata (LBA)......Page 505
  What We Have Learned So Far......Page 507
  Solved Problems......Page 508
  Multiple Choice Questions......Page 509
  Exercise......Page 510
 10.1 TM Languages......Page 511
  10.1.2 Turing Decidable......Page 512
 10.2 Unrestricted Grammar......Page 513
  10.2.1 Turing Machine to Unrestricted Grammar......Page 514
 10.3 Modified Chomsky Hierarchy......Page 518
 10.4 Properties of Recursive and Recursively Enumerable Language......Page 519
 10.5 Undecidability......Page 524
 10.6 Reducibility......Page 528
 10.7 Post’s Correspondence Problem (PCP)......Page 536
 10.8 Modified Post Correspondence Problem......Page 538
  10.8.1 Reduction of MPCP to PCP......Page 540
  What We Have Learned So Far......Page 543
  Solved Problems......Page 544
  Multiple Choice Questions......Page 545
  GATE Questions......Page 546
  Exercise......Page 549
  11.1.1 Different Types of Functions......Page 551
 11.3 Recursive Function......Page 553
  11.4.1 Russell’s Paradox......Page 558
 11.5 Ackermann’s Function......Page 559
 11.6 Minimalization......Page 560
  11.7.1 Properties of a μ Recursive Function......Page 561
 11.8 l Calculus......Page 562
 11.10 The Rice Theorem......Page 563
  What We Have Learned So Far......Page 564
  Solved Problems......Page 565
  Multiple Choice Questions......Page 566
  Exercise......Page 567
  12.1.2 Space Complexity......Page 568
  12.2.1 Big Oh Notation......Page 569
  12.2.2 Big Omega (W) Notation......Page 570
  12.2.3 Theta Notation (Q)......Page 571
 12.3 Problems and Its Classification......Page 572
  12.4.2 Logarithmic Time Complexity......Page 573
  12.4.3 Linear Time Complexity......Page 574
  12.4.4 Quasilinear Time Complexity......Page 575
  12.4.5 Average Case Time Complexity......Page 576
  12.4.6 Polynomial Time Complexity......Page 578
  12.4.7 Super Polynomial Time Complexity......Page 579
 12.5 The Classes P......Page 581
 12.6 Non-polynomial Time Complexity......Page 582
 12.7 Polynomial Time Reducibility......Page 584
  12.8.1 Tractable and Intractable Problem......Page 585
 12.9 P = NP?—The Million Dollar Question......Page 586
  12.10.2 Circuit Satisfiability Problem (CSAT)......Page 587
 12.11 NP Complete......Page 590
  12.11.1 Cook–Levin Theorem......Page 591
  12.12.1 Properties of NP Hard Problems......Page 597
 12.13 Space Complexity......Page 599
  What We Have Learned So Far......Page 600
  Solved Problems......Page 601
  Multiple Choice Questions......Page 604
  GATE Questions......Page 605
  Exercise......Page 607
 13.2 Types of Compiler......Page 609
 13.3 Major Parts of Compiler......Page 610
  13.3.1 Lexical Analysis......Page 612
  13.3.2 Syntax Analysis......Page 613
  13.3.3 Parser......Page 615
  What We Have Learned So Far......Page 636
  GATE Questions......Page 637
  Exercise......Page 639
 14.1 Matrix Grammar......Page 640
  14.2.1 String Accepted by a PA......Page 642
  14.3.1 Characteristics of Cellular Automata......Page 644
  14.3.2 Applications of Cellular Automata......Page 647
References......Page 650
Index......Page 652