Theory of Computation

Preface 00 Foreward 00 Features of the Book 00 1. PRELIMINARIES 1 1.1 Introduction 1 1.2 Basic Concepts 1 1.2.1 Symbol 1 1.2.2 Alphabet 1 1.2.3 String (or Word) 2 1.3 Sets 2 1.3.1 Operations 3 1.3.2 Cardinality 7 1.3.3 Countable and Uncountable Sets 7 1.4 Relations 8 1.4.1 Properties 10 1.4.2 Closure Properties 10 1.5 Graph 11 1.5.1 Directed Graph (or Digraph) 12 1.5.2 Tree 13 1.6 Language 13 1.6.1 Formal Languages 14 1.7 Mathematical Induction 14 2. FINITE STATE MACHINES 20 2.1 Introduction 20 2.1.1 Concept of Basic Machine 21 2.2 Finite State Machine 22 2.2.1 Examples 22 2.2.2 Transition Diagram (or Transition Graph) 24 2.2.3 Transition Matrix 24 2.3 Finite Automata 29 2.3.1 Transition Graph 30 2.3.2 Functions 31 2.3.3 Acceptance of a String 32 2.3.4 Acceptance of a Language 32 2.3.5 Some Examples of FA as Acceptor 33 2.3.6 FA as Finite Control 35 2.4 Deterministic Finite Automata 36 2.5 Non-deterministic Finite Automata 36 2.6 Equivalence of NFA and DFA 37 2.6.1 NFA to DFA Conversion (Method I) 38 2.6.2 DFA Minimization 41 2.6.3 NFA to DFA Conversion (Method II) 43 2.7 NFA with ?-Transitions 47 2.7.1 Significance of NFA with ?-Transitions 49 2.7.2 State Transition Table for NFA with ?-Transitions 50 2.7.3 ?-Closure of a State 50 2.8 Equivalence of NFA and NFA with ?-Transitions 50 2.9 Equivalence of DFA and NFA with ?-Transitions 53 2.9.1 Indirect Conversion Method 53 2.9.2 Direct Conversion Method 55 2.10 Finite Automata with Output 57 2.10.1 Moore Machine 57 2.10.2 Mealy Machine 59 2.10.3 Finite State Transducer 63 2.11 Equivalence of Moore and Mealy Machines 63 2.11.1 Moore to Mealy Conversion 64 2.11.2 Mealy to Moore Conversion 66 2.11.3 Additional Examples on Moore and Mealy Machines 68 2.12 FSM Equivalence 75 2.12.1 Moore's Algorithm 75 2.13 DFA Minimization (Another Approach) 77 2.14 Properties and Limitations of FSM 79 2.15 Additional FSM Examples 80 2.16 Two-way Finite Automaton 83 3. REGULAR EXPRESSIONS 94 3.1 Introduction 94 3.2 Regular Expression Formalism 95 3.3 Examples of Regular Expressions 96 3.4 Equivalence of Regular Expressions and Finite Automata 102 3.4.1 Kleene's Theorem 102 3.4.2 Regular Expression to FA Conversion 103 3.4.3 DFA to Regular Expression Conversion 109 3.5 Regular Sets and their Closure Properties 120 3.5.1 Formal Definition for Regular Sets 120 3.5.2 Closure Properties of Regular Sets 120 3.6 Pumping Lemma for Regular Languages 121 3.6.1 Applications of Pumping Lemma 123 3.7 Decision Algorithms for Regular Sets 125 3.8 Applications of Regular Expressions and Finite Automata 126 3.8.1 Lexical Analyser 127 3.8.2 Text Editors 128 3.8.3 'grep' Command 128 3.9 Additional Examples 128 3.10 Myhill-Nerode Theorem 133 4. TURING MACHINES 139 4.1 Introduction 139 4.2 Elements of a Turing Machine 140 4.3 Turing Machine Formalism 141 4.4 Instantaneous Description 143 4.5 Transition Graph for Turing Machine 145 4.6 Solved Problems 146 4.7 Complexity of a Turing Machine 199 4.8 Composite and Iterative Turing Machines 200 4.9 Universal Turing Machine 203 4.10 Multi-tape Turing Machine 205 4.11 Multi-stack Turing Machine 206 4.12 Multi-track Turing Machine 206 4.13 Solvable, Semi-solvable, and Unsolvable Problems 207 4.14 Halting Problem 208 4.15 Recursively Enumerable and Recursive Languages 210 4.16 Functions 210 4.16.1 Total Recursive Functions 211 4.16.2 Partial Recursive Functions 211 4.17 Church's Turing Hypothesis 211 4.18 Post's Correspondence Problem 212 4.19 Additional Turing Machine Examples 213 4.20 Linear Bounded Automata 226 5. GRAMMARS 233 5.1 Introduction 233 5.2 Constituents of Grammar 234 5.3 Formal Definition of a Grammar 234 5.4 Grammar Notations 235 5.5 Derivation Process 236 5.5.1 Leftmost Derivation 236 5.5.2 Rightmost Derivation 237 5.5.3 Derivation Examples 238 5.6 Derivation Tree 239 5.7 Context-free Languages 240 5.7.1 Examples of CFLs 240 5.8 Ambiguous Context-free Grammar 252 5.8.1 Removal of Ambiguity 253 5.9 Simplification of CFG 257 5.9.1 Removal of Useless Symbols 257 5.9.2 Removal of Unit Productions 258 5.9.3 Elimination of ?-Productions 260 5.10 Normal Forms 265 5.10.1 Chomsky Normal Form 265 5.10.2 Greibach Normal Form 267 5.11 Chomsky Hierarchy 269 5.11.1 Unrestricted Grammar (Type-0 Grammar) 270 5.11.2 Context-sensitive Grammar (Type-1 Grammar) 270 5.11.3 Context-free Grammar (Type-2 Grammar) 271 5.11.4 Regular Grammar (Type-3 Grammar) 271 5.12 Equivalence of Right-linear and Left-linear Grammars 273 5.12.1 Conversion of Right-linear Grammar to Equivalent Left-linear Grammar 273 5.12.2 Conversion of Left-linear Grammar to Equivalent Right-linear Grammar 275 5.13 Equivalence of Regular Grammars and Finite Automata 277 5.13.1 Right-linear Grammar and FA 277 5.13.2 Left-linear Grammar and FA 280 5.14 Pumping Lemma for Context-free Languages 283 5.14.1 Application of Pumping Lemma 286 5.14.2 Ogden's Lemma 288 5.15 Kuroda Normal Form 288 5.16 Dyck Language 289 5.17 Derivation Graph 289 5.18 Applications of CFG 291 5.18.1 Parser (or Syntax Analyser) 291 5.19 Backus-Naur Form 292 6. PUSHDOWN STACK-MEMORY MACHINE 300 6.1 Introduction 300 6.2 Elements of a PDM 301 6.2.1 Pictorial Representation of PDM Elements 301 6.3 Pushdown Automata 302 6.4 Finite Automata vs PDA 304 6.4.1 Examples of PDA that Accept Regular Languages 304 6.4.2 Relative Computational Powers of PDA and FA 307 6.5 PDA Accepting CFLs 307 6.5.1 Instantaneous Description of PDA 311 6.5.2 Acceptance of CFL by Empty Stack 312 6.5.3 Acceptance of CFL by Final State 312 6.5.4 State Transition Diagram for a PDA 312 6.6 DPDA vs NPDA 317 6.6.1 Relative Powers of DPDA/NPDA and NFA/DFA 320 6.7 Equivalence of CFG and PDA 321 6.7.1 NPDA Construction using Chomsky Normal Form 326 6.8 Closure Properties of CFLs 329 6.9 Additional PDA Examples 332 7. PARSING TECHNIQUES 339 7.1 Introduction 339 7.2 Introduction to Parsing 339 7.3 Top-down Parsing 340 7.3.1 Why Leftmost Derivation? 341 7.3.2 Working of a Top-down Parser 341 7.3.3 Some Potential Problems in Top-down Parsing and their Solutions 342 7.3.4 Recursive Descent Parsing 346 7.4 Bottom-up Parsing 350 7.4.1 Why Rightmost Reduction? 350 7.4.2 Working of a Bottom-up Parser 350 7.4.3 Operator Precedence Parsing 351 7.5 Automatic Construction of Bottom-up Parsers 352 7.5.1 LR(0) Grammar 352 7.5.2 SLR Parser 357 7.5.3 LR(1) Grammar 363 7.5.4 Canonical-LR Parser 365 7.5.5 LALR Parser 370 8. POST MACHINE 376 8.1 Introduction 376 8.2 Elements of Post Machine 376 8.3 Pushdown Stack-memory Machine vs Post Machine 377 8.4 Pictorial Representation of Post Machine Elements 378 8.5 Finite State Machine vs Post Machine 379 8.6 Post Machine that Accepts Context-free Languages 381 8.7 Non-deterministic Post Machine 390 8.8 Post Machine that Accepts Non-CFLs 394 9. UNDECIDABILITY 405 9.1 Introduction 405 9.2 Recursive and Recursively Enumerable Languages 405 9.2.1 Some Important Results with Recursive and RE Languages 406 9.3 Gödel Numbering (or Gödel Encoding) 408 9.3.1 Encoding of Turing Machines 408 9.4 Non-recursively Enumerable Languages 409 9.4.1 Diagonalization Language 410 9.4.2 Ld not Recursively Enumerable 410 9.5 Universal Language 411 9.6 Reducibility and Undecidable Problems 411 9.7 Rice's Theorem 412 9.8 Post's Correspondence Problem 413 9.9 Undecidable Problems for Context-free grammars 413 9.10 Greibach's Theorem 414 9.11 Hilbert's Problem 415 9.12 Ackermann's Function 416 10. COMPLEXITY AND CLASSIFICATION OF PROBLEMS 421 10.1 Introduction 421 10.2 Complexity of a Problem 421 10.2.1 Mathematical Notations for Time Complexity Measure 422 10.2.2 Time and Space Complexity of a Turing Machine 424 10.3 Classification of Problems 424 10.3.1 Non-deterministic Algorithm 424 10.3.2 Satisfiability 425 10.3.3 P-type and NP-type Problems 426 11. PRODUCTION SYSTEMS 431 11.1 Introduction 431 11.2 Post-Markov-Thue Production System 432 11.2.1 Formal Definition 433 11.2.2 Examples 433 11.3 Post Canonical System 436 11.4 Post Normal Form 437 11.5 Post-Markov-Thue System and Turing Machine 437 11.6 Post-Markov-Thue System and Finite State Machine 438 11.7 Markov Algorithm 440 11.7.1 Formal Definition 440 11.7.2 Examples 440 11.8 Labelled Markov Algorithm 447 11.8.1 Formal Definition 448 11.8.2 Some Examples 448 Appendix A: Implementations 453 Appendix B: Model Question Papers 512 Glossary 516 Bibliography 00 Index 00