You are previewing Introduction to Automata Theory, Formal Languages and Computation.
O'Reilly logo
Introduction to Automata Theory, Formal Languages and Computation

Book Description

Formal languages and automata theory is the study of abstract machines and how these can be used for solving problems. The book has a simple and exhaustive approach to topics like automata theory, formal languages and theory of computation. These descriptions are followed by numerous relevant examples related to the topic. A brief introductory chapter on compilers explaining its relation to theory of computation is also given.

Table of Contents

  1. Cover
  2. Title Page
  3. Contents
  4. About the Author
  5. Dedication
  6. Foreword
  7. Preface
  8. Chapter 1: Basic Terminology
    1. Introduction
    2. 1.1 Basics of String
    3. 1.2 Basics of Set Theory
      1. 1.2.1 Subset
      2. 1.2.2 Finite and Infinite Set
      3. 1.2.3 Equal
      4. 1.2.4 Algebraic Operations on Sets
      5. 1.2.5 Properties Related to Basic Operation
    4. 1.3 Relation on Set
    5. 1.4 Graph and Tree
      1. 1.4.1 Graph
      2. 1.4.2 Incident and Degree of a Vertex
      3. 1.4.3 Isolated Vertex, Pendant Vertex
      4. 1.4.4 Walk
      5. 1.4.5 Path and Circuit
      6. 1.4.6 Connected and Disconnected Graph
      7. 1.4.7 Tree
    6. 1.5 Basics of Digital Electronics
    7. 1.6 Digital Circuit
    8. 1.7 Basics of Automata Theory and Theory of Computation
    9. 1.8 History of Automata Theory
    10. 1.9 Use of Automata
    11. What We Have Learned So Far
    12. Solved Problems
    13. Fill in the Blanks
    14. Exercise
  9. Chapter 2: Language and Grammar
    1. Introduction
    2. 2.1 Grammar
    3. 2.2 The Chomsky Hierarchy
    4. What We Have Learned So Far
    5. Solved Problems
    6. Multiple Choice Questions
    7. GATE Questions
    8. Fill in the Blanks
    9. Exercise
  10. Chapter 3: Finite Automata
    1. Introduction
    2. 3.1 History of the Automata Theory
    3. 3.2 Use of Automata
    4. 3.3 Characteristics of Automaton
      1. 3.3.1 Characteristics
    5. 3.4 Finite Automata
    6. 3.5 Graphical and Tabular Representation FA
    7. 3.6 Transitional System
      1. 3.6.1 Acceptance of a String by Finite Automata
    8. 3.7 DFA and NFA
    9. 3.8 Conversion of an NFA to a DFA
      1. 3.8.1 Process of Converting an NFA to a DFA
    10. 3.9 NFA with ∈(null) Move
      1. 3.9.1 Usefulness of NFA with ∈ Move
      2. 3.9.2 Conversion of an NFA with ∈ Moves to DFA without ∈ Move
    11. 3.10 Equivalence of DFA and NFA
    12. 3.11 Dead State
    13. 3.12 Finite Automata with Output
      1. 3.12.1 The Mealy Machine
      2. 3.12.2 The Moore Machine
      3. 3.12.3 Tabular and Transitional Representation of the Mealy and Moore Machines
    14. 3.13 Conversion of One Machine to Another
      1. 3.13.1 Tabular Format
      2. 3.13.2 Transitional Format
    15. 3.14 Minimization of Finite Automata
      1. 3.14.1 Process of Minimizing
    16. 3.15 Myhill–Nerode Theorem
      1. 3.15.1 Equivalence Relation
      2. 3.15.2 Statement of the Myhill–Nerode Theorem
      3. 3.15.3 Myhill–Nerode Theorem in Minimizing a DFA
    17. 3.16 Two-way Finite Automata
    18. 3.17 Application of Finite Automata
    19. 3.18 Limitations of Finite Automata
    20. What We Have Learned So Far
    21. Solved Problems
    22. Multiple Choice Questions
    23. GATE Questions
    24. Fill in the Blanks
    25. Exercise
  11. Chapter 4: Finite State Machine
    1. Introduction
    2. 4.1 Sequence Detector
    3. 4.2 Binary Counter
      1. 4.2.1 Designing Using Flip Flop (T Flip Flop and SR Flip Flop)
    4. 4.3 Finite State Machine
      1. 4.3.1 Capabilities and Limitations of Finite-State Machine
    5. 4.4 State Equivalence and Minimization of Machine
    6. 4.5 Incompletely Specified Machine, Minimal Machine
      1. 4.5.1 Simplification
    7. 4.6 Merger Graph
    8. 4.7 Compatibility Graph and Minimal Machine Construction
      1. 4.7.1 Compatible Pair
      2. 4.7.2 Implied Pair
      3. 4.7.3 Compatibility Graph
      4. 4.7.4 Minimal Machine Construction
      5. 4.7.5 Minimal Machine
    9. 4.8 Merger Table
      1. 4.8.1 Construction of a Merger Table
    10. 4.9 Finite Memory and Definite Memory Machine
      1. 4.9.1 Finite Memory Machine
      2. 4.9.2 Constructing the Method of Connection Matrix
      3. 4.9.3 Vanishing of Connection Matrix
      4. 4.9.4 Definite Memory machine
    11. 4.10 Information Lossless Machine
      1. 4.10.1 Test for Information Losslessness
    12. 4.11 Inverse Machine
    13. 4.12 Minimal Inverse Machine
    14. What We Have Learned So Far
    15. Solved Problems
    16. Multiple Choice Questions
    17. Fill in the Blanks
    18. Exercise
  12. Chapter 5: Regular Expression
    1. Introduction
    2. 5.1 Basics of Regular Expression
      1. 5.1.1 Some Formal Recursive Definitions of RE
    3. 5.2 Basic Operations on Regular Expression
      1. 5.2.1 Kleene’s Closure
    4. 5.3 Identities of Regular Expression
    5. 5.4 The Arden’s Theorem
      1. 5.4.1 Process of Constructing Regular Expression from Finite Automata
    6. 5.5 Construction of Finite Automata from a Regular Expression
      1. 5.5.1 Conversion of an RE to NFA with ∈ transition
      2. 5.5.2 Direct Conversion of RE to DFA
    7. 5.6 NFA with ∈ Move and Conversion to DFA by ∈ -Closure Method
      1. 5.6.1 Conversion of an NFA with ∈ move to a DFA
    8. 5.7 Equivalence of Two Finite Automata
    9. 5.8 Equivalence of Two Regular Expressions
    10. 5.9 Construction of Regular Grammar from an RE
    11. 5.10 Constructing FA from Regular Grammar
    12. 5.11 Pumping Lemma for Regular Expression
    13. 5.12 Closure Properties of Regular Set
    14. 5.13 Decision Problems of Regular Expression
    15. 5.14 ‘Grep’ and Regular Expression
    16. 5.15 Application of Regular Expression
    17. What We Have Learned So Far
    18. Solved Problems
    19. Multiple Choice Questions
    20. GATE Questions
    21. Fill in the Blanks
    22. Exercise
  13. Chapter 6: Context-free Grammar
    1. Introduction
    2. 6.1 Definition of Context-free Grammar
      1. 6.1.1 Backus Naur Form (BNF)
    3. 6.2 Derivation and Parse Tree
      1. 6.2.1 Derivation
      2. 6.2.2 Parse Tree
    4. 6.3 Ambiguity in Context-free Grammar
    5. 6.4 Left Recursion and Left Factoring
      1. 6.4.1 Left Recursion
      2. 6.4.2 Left Factoring
    6. 6.5 Simplification of Context-free Grammar
      1. 6.5.1 Removal of Useless Symbols
      2. 6.5.2 Removal of Unit Productions
      3. 6.5.3 Removal of Null Productions
    7. 6.6 Linear Grammar
      1. 6.6.1 Right Linear to Left Linear
      2. 6.6.2 Left Linear to Right Linear
    8. 6.7 Normal Form
      1. 6.7.1 Chomsky Normal Form
      2. 6.7.2 Greibach Normal Form
    9. 6.8 Closure Properties of Context-free Language
      1. 6.8.1 Closed Under Union
      2. 6.8.2 Closed Under Concatenation
      3. 6.8.3 Closed Under Star Closure
      4. 6.8.4 Closed Under Intersection
      5. 6.8.5 Not Closed Under Complementation
      6. 6.8.6 Every Regular Language is a Context-free Language
    10. 6.9 Pumping Lemma for CFL
    11. 6.10 Ogden’s Lemma for CFL
    12. 6.11 Decision Problems Related to CFG
      1. 6.11.1 Emptiness
      2. 6.11.2 Finiteness
      3. 6.11.3 Membership Problem
    13. 6.12 CFG and Regular Language
    14. 6.13 Applications of Context-free Grammar
    15. What We Have Learned So Far
    16. Solved Problems
    17. Multiple Choice Questions
    18. GATE Questions
    19. Fill in the Blanks
    20. Exercise
  14. Chapter 7: Pushdown Automata
    1. Introduction
    2. 7.1 Basics of PDA
      1. 7.1.1 Definition
      2. 7.1.2 Mechanical Diagram of the PDA
    3. 7.2 Acceptance by a PDA
      1. 7.2.1 Accepted by an Empty Stack (Store)
      2. 7.2.2 Accepted by the Final State
    4. 7.3 DPDA and NPDA
      1. 7.3.1 Deterministic Pushdown Automata (DPDA)
      2. 7.3.2 Non-deterministic Pushdown Automata (NPDA)
    5. 7.4 Construction of PDA from CFG
    6. 7.5 Construction of CFG Equivalent to PDA
    7. 7.6 Graphical Notation for PDA
    8. 7.7 Two-stack PDA
    9. What We Have Learned So Far
    10. Solved Problems
    11. Multiple Choice Questions
    12. GATE Questions
    13. Fill in the Blanks
    14. Exercise
  15. Chapter 8: Turing Machine
    1. Introduction
    2. 8.1 Basics of Turing Machine
      1. 8.1.1 Mechanical Diagram
      2. 8.1.2 Instantaneous Description (ID) in Respect of TM
    3. 8.2 Transitional Representation of Turing Machine
    4. 8.3 Non-deterministic Turing Machine
    5. 8.4 Conversion of Regular Expression to Turing Machine
    6. 8.5 Two-stack PDA and Turing Machine
      1. 8.5.1 Minsky Theorem
    7. What We Have Learned So Far
    8. Solved Problems
    9. Multiple Choice Questions
    10. GATE Questions
    11. Fill in the Blanks
    12. Exercise
  16. Chapter 9: Variations of the Turing Machine
    1. Introduction
    2. 9.1 Variations of the Turing Machine
      1. 9.1.1 Multi-tape Turing Machine
      2. 9.1.2 Multi-head Turing Machine
      3. 9.1.3 Two-way Infinite Tape
      4. 9.1.4 K-dimensional Turing Machine
      5. 9.1.5 Non-deterministic Turing Machine
      6. 9.1.6 Enumerator
    3. 9.2 Turing Machine as an Integer Function
    4. 9.3 Universal Turing Machine
    5. 9.4 Linear-Bounded Automata (LBA)
    6. 9.5 Post Machine
    7. 9.6 Church’s Thesis
    8. What We Have Learned So Far
    9. Solved Problems
    10. Multiple Choice Questions
    11. GATE Questions
    12. Exercise
  17. Chapter 10: Computability and Undecidability
    1. Introduction
    2. 10.1 TM Languages
      1. 10.1.1 Turing Acceptable
      2. 10.1.2 Turing Decidable
    3. 10.2 Unrestricted Grammar
      1. 10.2.1 Turing Machine to Unrestricted Grammar
      2. 10.2.2 Kuroda Normal Form
      3. 10.2.3 Conversion of a Grammar into the Kuroda Normal Form
    4. 10.3 Modified Chomsky Hierarchy
    5. 10.4 Properties of Recursive and Recursively Enumerable Language
    6. 10.5 Undecidability
    7. 10.6 Reducibility
    8. 10.7 Post’s Correspondence Problem (PCP)
    9. 10.8 Modified Post Correspondence Problem
      1. 10.8.1 Reduction of MPCP to PCP
    10. What We Have Learned So Far
    11. Solved Problems
    12. Multiple Choice Questions
    13. GATE Questions
    14. Exercise
  18. Chapter 11: Recursive Function
    1. Introduction
    2. 11.1 Function
      1. 11.1.1 Different Types of Functions
    3. 11.2 Initial Functions
    4. 11.3 Recursive Function
    5. 11.4 Gödel Number
    6. 11.4.1 Russell’s Paradox
    7. 11.5 Ackermann’s Function
    8. 11.6 Minimalization
    9. 11.7 μ Recursive
      1. 11.7.1 Properties of a μ Recursive Function
    10. 11.8 λ Calculus
    11. 11.9 Cantor Diagonal Method
    12. 11.10 The Rice Theorem
    13. What We Have Learned So Far
    14. Solved Problems
    15. Multiple Choice Questions
    16. Exercise
  19. Chapter 12: Computational Complexity
    1. Introduction
    2. 12.1 Types of Computational Complexity
      1. 12.1.1 Time Complexity
      2. 12.1.2 Space Complexity
    3. 12.2 Different Notations for Time Complexity
      1. 12.2.1 Big Oh Notation
      2. 12.2.2 Big Omega (Ω) Notation
      3. 12.2.3 Theta Notation (Θ)
      4. 12.2.4 Little-oh Notation (o)
      5. 12.2.5 Little Omega Notation (ω)
    4. 12.3 Problems and Its Classification
    5. 12.4 Different Types of Time Complexity
      1. 12.4.1 Constant Time Complexity
      2. 12.4.2 Logarithmic Time Complexity
      3. 12.4.3 Linear Time Complexity
      4. 12.4.4 Quasilinear Time Complexity
      5. 12.4.5 Average Case Time Complexity
      6. 12.4.6 Polynomial Time Complexity
      7. 12.4.7 Super Polynomial Time Complexity
    6. 12.5 The Classes P
    7. 12.6 Non-polynomial Time Complexity
    8. 12.7 Polynomial Time Reducibility
    9. 12.8 Deterministic and Non-deterministic Algorithm
      1. 12.8.1 Tractable and Intractable Problem
    10. 12.9 P = NP?—The Million Dollar Question
    11. 12.10 SAT and CSAT Problem
      1. 12.10.1 Satisfiability Problem (SAT)
      2. 12.10.2 Circuit Satisfiability Problem (CSAT)
    12. 12.11 NP Complete
      1. 12.11.1 Cook–Levin Theorem
    13. 12.12 NP Hard
      1. 12.12.1 Properties of NP Hard Problems
    14. 12.13 Space Complexity
    15. What We Have Learned So Far
    16. Solved Problems
    17. Multiple Choice Questions
    18. GATE Questions
    19. Exercise
  20. Chapter 13: Basics of Compiler Design
    1. Introduction
    2. 13.1 Definition
    3. 13.2 Types of Compiler
      1. 13.2.1 Difference Between Single Pass and Multi Pass Compiler
    4. 13.3 Major Parts of Compiler
      1. 13.3.1 Lexical Analysis
      2. 13.3.2 Syntax Analysis
      3. 13.3.3 Parser
    5. What We Have Learned So Far
    6. Multiple Choice Questions
    7. GATE Questions
    8. Exercise
  21. Chapter 14: Advance Topics Related to Automata
    1. Introduction
    2. 14.1 Matrix Grammar
    3. 14.2 Probabilistic Finite Automata
      1. 14.2.1 String Accepted by a PA
    4. 14.3 Cellular Automata
      1. 14.3.1 Characteristics of Cellular Automata
      2. 14.3.2 Applications of Cellular Automata
  22. References
  23. Acknowledgements
  24. Copyright
  25. Back Cover