Introduction to Automata Theory, Formal Languages and Computation

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