Kulkarni, V: Theory of Computation

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 Godel Numbering (or Godel 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