Theory of Computation Simplified: Simulate Real-world Computing Machines and Problems with Strong Principles of Computation

Cover Page
Title Page
Copyright Page
Dedication Page
About the Authors
About the Reviewer
Acknowledgements
Preface
Errata
Table of Contents
1. Finite Automata
    Structure
    Objectives
    1.1 Introduction to Formal language
    1.2 Introduction to Language Translation Logic
    1.3 Essentials of Translation
    1.4 Alphabets and languages
        1.4.1 An Alphabet (Σ)
        1.4.2 Languages (L)
    1.5 Finite Representation of Language
        1.5.1 Operations of Languages
    1.6 Finite Automata (FA)
        1.6.1 Basic Machine
        1.6.2 Constructing Simple Automata
        1.6.3 Handle End Conditions
        1.6.4 Handling Reject States
        1.6.5 A Step-by-Step Method for Constructing Automata
        1.6.6 States as Memory
    1.7 Finite State Machine (FSM)
    1.8 Language Accepted by Finite Automata
    1.9 Definition of Regular Language
        1.9.1 Kleene’s Theorem
        1.9.2 Regular Set
    1.10 Definition of Finite Automata
        1.10.1 Representation
    1.11 Deterministic Finite Automata
        1.11.1 Definition of a Deterministic Finite Automaton
        1.11.2 How does a DFA Process Strings?
        1.11.3 Simple Notations for DFAs
        1.11.4 Extending Transition Function to Strings
        1.11.5 The Language of DFA
    1.12 Finite Automata with Output
        1.12.1 Moore Machine
        1.12.2 Mealy Machine
        1.12.3 Inter Conversion
    1.13 Minimization of Automata
        13.4.1 Table-Filling Algorithm
    1.14 FA properties
        1.14.1 Equivalence of Finite Automata
        1.14.2 ϵ-Transitions
            1.14.2.1 Generalized Non-deterministic Finite Automata
    1.15 Limitations of Finite Automata
    Practice Examples
    Conclusion
    Points to Remember
    Exercise
    Multiple Choice Questions
        Answers
    Programming Problems:
2. Non-Deterministic Finite Automata
    Structure
    Objectives
    2.1 Non-deterministic Finite Automata (NFA)
        2.1.1 Definition of NFA
        2.1.2 The extended Transition Function
        2.1.3 The Language of NFA
        2.1.4 Equivalence of Deterministic and Non-deterministic Finite Automata
        2.1.5 Finite Automata with ε-Moves
    2.2 Constructing NFA
        2.2.1 Conversion of NFA with-ε to NFA without-ε
        2.2.2 Indirect Method
    2.3 Eliminating Non-Determinism -Conversion of NFA to DFA
    2.4 Limitations of NFA
    2.5 Applications of NFA
    Practice Examples
    Conclusion
    Points to Remember
    Exercises
    Multiple Choice Questions
        Answers
    Programming Problems
3. Regular Expressions
    Structure
    Objectives
    3.1 Introduction
    3.2 Regular Expressions
        3.2.1 Definition
        3.2.1 Language Defined by Regular Expressions
        3.2.2 Formulating Regular Expressions
        3.2.3 Precedence of Operators
    3.3 Algebraic Laws of Regular Expressions
        3.3.1 Identities and Annihilators
        3.3.2 Idempotent laws and laws involving closures
        3.3.3 Commutative and associative laws
        3.3.4 Distributive laws
        3.3.5 Arden’s Law
        3.3.6 Miscellaneous
    3.4 Finite Automata and Regular Expressions
        3.4.1 Conversion of Regular Expressions to DFA
        3.4.1 RE to DFA (Indirect Method)
        3.4.2 RE to DFA (Direct method)
    3.5 Conversion of DFA to Regular Expressions
        3.5.1 State/Loop Elimination Method
        3.5.2 Arden’s theorem
    3.6 Equivalence of Regular Expressions
    3.7 Applications of Regular Expressions
        3.7.1 RE in text search and replace
        3.7.2 String Validation
        3.7.3 Tokenization
    Practice Examples
    Conclusion
    Points to Remember
    Exercises
    Multiple Choice Questions
        Answers
    Programming Problems:
4. Context Free Grammars
    Structure
    Objectives
    4.1 Introduction
    4.2 The Grammar - Basic Element and Definition
        4.2.1 Language Generated by the Grammar
    4.3 The Context Free Grammar
        4.3.1 Definition of context free grammar
        4.3.2 Derivation using Grammar
        4.3.3 Leftmost and Rightmost Derivations
        4.3.4 The Language of a Grammar
        4.3.5 Sentential Forms
    4.4 The Parse Tree and Derivation
        4.4.1 Constructing Parse tree
    4.5 Ambiguity in Grammars and Languages
        4.5.1 Ambiguous Grammars
        4.5.2 Removing Ambiguity from Grammars
        4.4.3 Inherent Ambiguity
    4.6 Simplification of Grammar
        4.6.1 Elimination of Useless Symbols
            4.6.1.1 Computing the Generating and Reachable Symbols
        4.6.2 Eliminating ε-productions
        4.6.3 Eliminating the Unit Productions
    4.7 Normal forms
        4.7.1 Chomsky Normal Form
        4.7.2 Greibach Normal Form (GNF)
    4.7 Properties of CFL
    4.8 Chomsky Hierarchy
        4.8.1 Type 0 or unrestricted (all possible grammars)
        4.8.2 Type 2 or Context-free Grammars
        4.8.3 Type 3 or Regular
    4.9 Applications of CFG
        4.9.1 Parser Design
            4.9.1.1 Yacc
        4.9.2 Markup Languages
        4.9.3 XML and Document Type Definition
        Solved Examples
    Conclusion
    Points to Remember
    Exercises
    Multiple Choice Questions
        Answers
    Programming Assignment:
5. Regular Languages
    Structure
        Objectives
    5.1 Regular Language
    5.2 Grammars for Regular Languages
    5.3 Regular Grammar and Finite Automata
    5.4 Conversion of Automata to Regular Grammars
    5.5 Conversion of Regular Grammars to Automata
    5.6 Inter-conversion between Left Linear GL and Right Linear GR Regular Grammar329
        5.6.1 Conversion of Right Linear GR to Left Linear GL
        5.6.2 Left Linear GL to Right Linear GR
        5.6.3 Construction of finite automata from a Left Linear Grammar
    5.7 Properties of Regular Languages
        5.7.1 Pumping Lemma Proving Languages not to be regular
            5.7.1.1 Languages that are and are not regular
            5.7.1.2 Pumping Lemma
            5.7.1.3 Checking whether given language is regular or not
    5.8 Closure Properties of Regular Languages
        5.8.1 Decision Properties of Regular Languages
    Solved Examples
    Conclusion
    Exercises
    Multiple Choice Questions
        Answers
    Programming Questions
6. Push Down Automata
    Structure
    Objectives
    6.1 Introduction
    6.2 Push down Automata
        6.2.1 Definition
        6.2.2 A Graphical Notation for PDAs
        6.2.3 Instantaneous Description of a PDA
    6.3 Language of Push down Automata
        6.3.1 Acceptance by Final State
        6.3.2 Acceptance by Empty Stack
    6.4 Pictorial Representation of PDA
        6.4.1 Adding a Pushdown Stack
    6.5 Equivalence of PDA and CFG
        6.5.1 Conversion of CFG to PDA
        6.5.2 Construction of (pictorial) PDA from CFG
        6.5.3 Conversion of PDA to CFG
    6.6 Deterministic Push down Automata (DPDA)
        6.6.1 Definition of DPDA
        6.6.2 Regular language and DPDA
        6.6.3 Deterministic Push down Automata and Context Free Languages
        6.6.4 DPDAs and Ambiguous Grammar
    6.7 Non-deterministic Push down Automata
        6.7.1 Formal Definition of NPDA
            6.7.1.1 Transition Function for NPDAs
        6.7.2 Drawing NPDAs
            6.7.2.1 NPDA Execution
            6.7.2.2 Accepting Strings with an NPDA
    6.8 Multi-stack PDA
    6.9 A Pumping Lemma for Context-free Languages
        6.9.1 Statement of the pumping lemma
        6.9.2 Preliminary Definitions
        6.9.3 Proving the Pumping Lemma, (Part I)
        6.9.4 Providing the Pumping Lemma, (Part II)
        6.9.5 Using the Pumping Lemma
    6.10 Closure Properties of CFL
    6.11 Decision Properties of Context Free Languages
    Solved Exercises
    Conclusion
    Points to Remember
    Exercises
    Multiple Choice Questions
        Answers
    Programming Questions
7. Post Machines
    Structure
    Objectives
    7.1 Post Machines
    7.2 Deterministic Post Machine (DPM)
        7.2.1 Definition
        7.3 Language of Post Machine
    7.4 Non-deterministic Post Machine (NPM)
    7.5 Power of Post Machine
    Conclusion
    Point to Remember
    Exercises
    Multiple Choice Questions
        Answers
    Programming Questions
8. Turing Machines
    Structure
    Objectives
    8.1 Problems That Computers Cannot Solve
    8.2 The Turing Machine
        8.2.1 Instantaneous Description (ID) of the Turing Machine
        8.2.2 The Language of Turing Machine
        8.2.3 Transition Diagrams and Transition Table for Turing Machine
        8.2.4 Turing Machine and Halting
    8.3 Programming Techniques for Turing Machine
        8.3.1 Storage in the State
        8.3.2 Multiple Tracks
        8.3.3 Subroutines
    8.4 Extensions to Basic Turing Machine
        8.4.1 Multitape Turing Machines
        8.4.2 Non-deterministic Turing Machines
    8.5 Turing Machine and Computers
        8.5.1 Simulating a Turing Machine by Computer
        8.5.2 Simulating a Computer by a Turing Machine
    8.6 Recursive Languages
        8.6.1 Difference between Recursive and recursively enumerable language
    8.7 Composite Turing Machine
    8.8 Iterated Turing Machine
    8.9 Universal Turing Machine (UTM)
        8.9.1 Turing Machine Codes
    8.10 Turing Machine Limitations (Unsolvability)
        8.10.1 The Halting Problem
        8.10.2 Consequences of the Halting Problem
    8.11 Solvability, Semi-Solvability, and Unsolvability
    8.12 Functions - Total and Partial Functions
    8.13 Primitive Recursive Functions and Recursive Functions
        8.13.1 Composition
        8.13.2 Recursion
        8.13.3 Primitive Recursive Function over N
        8.13.4 Primitive Recursive Functions Over {a, b}
    8.14 Recursive Functions
    8.15 Comparison of Machines
    8.16 Grammar and Machine
    Conclusion
    Points to Remember
    Exercise
    Multiple Choice Questions
        Answers
    Programming Questions
9. Computability and Undecidability
    Structure
    Objectives
    9.1 Un-decidability
        9.1.1 A Language that is not Recursively Enumerable
    9.2 An un-decidability problem that is recursively enumerable
        9.2.1 A Proof by a Generic Approach
            9.2.1.1 Proofs by Reduction
    9.3 An Undecidable Problem that is Recursively Enumerable
        9.3.1 Recursive Languages
        9.3.2 Complements of Recursive and RE Languages
            9.3.2.1 The Universal Language
    9.4 Post Correspondence Problem (PCP)
        9.4.1 A Modified PCP (MPCP)
    9.5 Intractable versus Intractable Problems
    9.6 Church-Turing Thesis
    9.7 Analyzing Algorithms - Asymptotic Notations
        9.7.1 O-Notation(O)
        9.7.2 Omega Notation (Ω)
        9.7.3 Theta Notation(θ)
    9.8 Complexity Classes and Relations
    9.9 The Class P
        9.9.1 Problems solvable in Polynomial Time
        9.9.2 An Example - Kruskal’s Algorithm
    9.10 The Class NP
        9.10.1 Non-deterministic Polynomial Time
        9.10.2 Travelling Salesman Problem
        9.10.3 Polynomial Time Reductions
    9.11 NP Complete Problems
    9.12 Various NP- Complete Problems
        9.12.1 Satisfiability Problem
        9.12.2 Vertex Cover Problem/Node Cover Decision Problem (NCDP)
    Conclusion
    Points to Remember
    Exercises
    Multiple choice questions
        Answers
10. Complexity Theory - Advanced Perspective
    Structure
    Objectives
    10.1 Problem Solving and Algorithmic Computing
        10.1.1 Problem Solving Strategies
            10.1.1.1 Divide and Conquer
            10.1.1.2 Backtracking
            10.1.1.3 Branch and Bound
            10.1.1.4 Dynamic Programming
            10.1.1.5 Greedy Approach
        10.1.2 Defining Algorithm
        10.1.3 Characteristics of an Algorithm
        10.1.4 Algorithmics
    10.2 Approximation Algorithms
        10.2.1 Solving TSP by Approximation Algorithm
        10.2.2 Approximating Max Clique
    10.3 Randomized Algorithms
        10.3.1 Randomized Sorting Algorithm
    10.4 Probabilistic Algorithms
    10.5 Parallel Algorithm
        10.5.1 Sequential and Parallel Computing
        10.5.2 Speedup
        10.5.2.1 Amdahl’s Law for Multiprocessor Systems
        10.5.3 Work and Efficiency
            10.5.3.1 Brent’s Theorem
        10.5.4 Computational Model for Parallel Algorithm
            10.5.4.1 Read and Write Techniques in PRAM
    Conclusion
    Points to Remember
    Exercise
    Multiple Choice Questions
        Answers
Index