Theory of Computation

[BOOK 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.

[TABLE OF CONTENTS]

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