Theory of Computation

Vivek Kulkarni

Presents each procedure in the text in algorithmic form for the reader to learn the concepts in any programming language of their own choice.
Includes several solved examples in each chapter for better recapitulation of the concepts learnt.
Provides numerous objective type questions with answers, review questions, and exercises at the end of every chapter, graded as per Bloom's taxonomy principles.
Includes appendices containing the implementation details and 'C' source code for all the key algorithms discussed in the book and five model question papers to help students prepare for their university examinations.

Theory of Computation

Vivek Kulkarni

Description

The book begins with basic concepts such as symbols, alphabets, sets, relations, graphs, strings, and languages. It then delves into the important topics including separate chapters on finite state machine, regular expressions, grammars, pushdown stack, Turing machine, parsing techniques, Post machine, undecidability, and complexity of problems. A chapter on production systems encompasses a computational model which is different from the Turing model, called Markov and labelled Markov algorithms. At the end, the chapter on implementations provides implementation of some key concepts especially related to regular languages using C program codes.

A highly detailed pedagogy entailing plenty of solved examples, figures, notes, flowcharts, and end-chapter exercises makes the text student-friendly and easy to understand.

Theory of Computation

Vivek Kulkarni

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 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

Theory of Computation

Vivek Kulkarni

Author Information

Vivek Kulkarni, Principal Architect, Persistent Systems Ltd., Pune

Vivek Kulkarni is currently working as Principal Architect in Persistent Systems Ltd. He has more than 18 years of experience in academia and software industry. He has served as a subject chairman for multiple subjects for the Board of Computer Engineering, University of Pune. He has also worked in organizations such as BMC Software, Symantec Corporation, and Tech-Mahindra. He is also one of the inventors for System and Method of Universal Programming Language Conversion, which has been internationally recognized and patented.