Formal Language and Automata Theory

Cover
Copyright
Contents
Preface
Acknowledgements
List of Important Symbols
List of Important Abbreviations
About the Authors
1. Mathematical Preliminaries and Formal Languages
	1.1 Set Theory
		1.1.1 Describing a Set
		1.1.2 Empty Set
		1.1.3 Identity and Cardinality
		1.1.4 Subset
		1.1.5 Power Sets
		1.1.6 Operations on Sets: Union, Intersection
		1.1.7 Set Theoretic Equalities
		1.1.8 Sequence Versus Set
		1.1.9 Ordered Pairs
		1.1.10 Cartesian Product
	1.2 Relations
		1.2.1 Binary Relation
		1.2.2 Domain and Range of Relation
		1.2.3 Operations on Relations
		1.2.4 Properties of Relations
	1.3 Functions
		1.3.1 Definitions
		1.3.2 Types of Functions
	1.4 Alphabet, String and Language
		1.4.1 Operations on Language
		1.4.2 Grammars
		1.4.3 Types of Grammars–Chomsky Hierarchy
	1.5 Graphs and Trees
		1.5.1 Directed Graph
		1.5.2 Undirected Graph
		1.5.3 Trees
	1.6 Theorem Proving
		1.6.1 Proof by Induction
		1.6.2 Proof by Contradiction
		1.6.3 Proof by Example
	Summary
	Short Answers
	Fill in the Blanks
	Objective Question Bank
	Exercises
2. Finite Automata
	2.1 Finite-state Machine
		2.1.1 Finite-Automaton Model
		2.1.2 Properties of Transition Function ‘c’
		2.1.3 Transition Diagram
		2.1.4 Transition Table
	2.2 Language Acceptance
	2.3 Two Types of Finite Automata
		2.3.1 Deterministic Finite Automata (DFA)
		2.3.2 Non-deterministic Finite Automaton (NFA)
		2.3.3 Acceptance of NFA
	2.4 Equivalence of DFAs and NFAs
	2.5 Converting NFA (MN) to DFA (MD)—Subset Construction
	2.6 NFA with Epsilon-(e) Transitions
		2.6.1 Epsilon Closure (e-closure)
		2.6.2 Eliminating e-Transitions
		2.6.3 Converting NFA with e-Transition to NFA without e-Transition
		2.6.4 Converting NFA with e-Transition to DFA
	2.7 Comparison Method for Testing Equivalence of Two FAs
	2.8 Reduction of Number of States in FA
		2.8.1 Indistinguishable States
		2.8.2 Equivalent Classes
		2.8.3 Minimization of DFA
		2.8.4 Minimization of DFA Using Myhill Nerode Theorem
	2.9 Finite Automata with Output
		2.9.1 Moore Machine
		2.9.2 Mealy Machine
		2.9.3 Equivalence Between Moore and Mealy Machines
		2.9.4 Interconversions Between Machines
	2.10 Applications of Finite Automata with Output
		2.10.1 The Full-adder
		2.10.2 The String Sequence Detector
	Solved Problems
	Summary
	Short Answers
	Fill in the Blanks
	Objective Question Bank
	Exercises
3. Regular Languages and Regular Grammars
	3.1 Regular Expressions
	3.2 Regular Sets
	3.3 Identity Rules for Regular Expressions
	3.4 Algebraic Laws for Regular Expressions
	3.5 Equivalence of Finite Automata with Regular Expressions
	3.6 Constructing Regular Expression for Given DFA
		3.6.1 Arden’s Theorem
		3.6.2 Arden’s Theorem in Construction of RE
		3.6.3 Construction of RE Using Generalized NFA
	3.7 Pumping Lemma of Regular Expressions
		3.7.1 Formal Definition of the Pumping Lemma
	3.8 Regular Grammar
		3.8.1 Equivalence of Regular Grammar and Finite Automata
		3.8.2 Converting Finite Automaton to Regular Grammar
	3.9 Closure Properties of Regular Sets
	3.10 Applications of Regular Expressions
		3.10.1 Lexical Analysis
		3.10.2 Finding Patterns
	3.11 Decision Properties of Regular Languages
		3.11.1 Conversion from NFA to DFA
		3.11.2 Emptiness Membership and Equivalence
	Solved Problems
	Summary
	Short Answers
	Fill in the Blanks
	Objective Question Bank
	Exercises
4. Context Free Grammars and Context Free Languages
	4.1 Context Free Grammars
	4.2 Derivation of CFGs
	4.3 Understanding the Language Defined by Grammars
		4.3.1 Leftmost and Rightmost Derivations
		4.3.2 Derivation Tree
		4.3.3 Equivalence of Parse Trees and Derivations
	4.4 Ambiguous Grammar
		4.4.1 Removing Ambiguity
		4.4.2 Inherent Ambiguity
	4.5 Simplification of Grammars
		4.5.1 Elimination of Useless Symbols
		4.5.2 Elimination of e-Productions
		4.5.3 Eliminating Unit Productions
	4.6 Normal Forms
		4.6.1 The Chomsky Normal Form
		4.6.2 The Greibach Normal Form
	4.7 Pumping Lemma for CFL
		4.7.1 Lemma
	4.8 Decision Algorithms for CFLs
		4.8.1 Finiteness and Infiniteness
	4.9 Membership
	4.10 Closure Properties of CFLs
	4.11 Applications of CFG
	Solved Problems
	Summary
	Short Answers
	Fill in the Blanks
	Objective Question Bank
	Exercises
5. Push Down Automata
	5.1 Pushdown Automata
		5.1.1 Graphical Representation of PDA
		5.1.2 Instantaneous Description of PDA
		5.1.3 Language Acceptance by PDA
	5.2 Equivalence of Acceptance of Final State and Empty Stack
	5.3 Types of PDAs
		5.3.1 Deterministic PDA
		5.3.2 Closure Properties of DCFL
		5.3.3 Decision Properties of DCFLs
		5.3.4 DPDA and Regular Languages
		5.3.5 DPDA and Ambiguous Grammar
	5.4 Equivalence of PDA’s and CFG’s
		5.4.1 Constructing PDA for Given CFG
		5.4.2 Constructing CFG for the Given PDA
	5.5 Two-stack PDA
	5.6 Applications of PDA
		5.6.1 PDA as a Parser
		5.6.2 Top-down Parser Using the PDA
	Solved Problems
	Summary
	Short Answers
	Fill in the Blanks
	Objective Question Bank
	Exercises
6. Turing Machines
	6.1 Turing Assumptions
		6.1.1 Instantaneous Description
		6.1.2 Turing Machine as Language Accepter
	6.2 Turing Machine as a Computational Machine
	6.3 Techniques for Turing Machine Construction
		6.3.1 Storage in Finite Control
		6.3.2 Multi-track Tape
		6.3.3 Checking off Symbols
		6.3.4 Subroutines
		6.3.5 Shifting Over
	6.4 Types of Turing Machines
		6.4.1 Non-deterministic Turing Machines
		6.4.2 Turing Machines with Two-dimensional Tapes
		6.4.3 Turing Machines with Multiple Tapes
		6.4.4 Turing Machines with Multiple Heads
		6.4.5 Turing Machines with Infinite Tape
	6.5 Church’s Thesis
	6.6 Turing Machines as Enumerators
	6.7 Universal Turing Machine
	6.8 Counter Machine
	6.9 Recursive and Recursively Enumerable Languages
	6.10 Linear Bound Automata and Context Sensitive Language
		6.10.1 Equivalence of LBA’s and CSG’s
	Solved Problems
	Summary
	Short Answers
	Fill in the Blanks
	Objective Question Bank
	Exercises
7. Undecidability and Computability
	7.1 Decision Problems
	7.2 Decidability and Decidable Languages
		7.2.1 Decidable Problems Concerning Regular Languages
		7.2.2 Decidable Problems Concerning Context Free Languages
	7.3 Halting Problem
		7.3.1 The Halting Problem for Turing Machines
	7.4 Diagonalization Method
		7.4.1 Undecidable Problems
	7.5 Post’s Correspondence Problem
		7.5.1 The Undecidability of Post’s Correspondence Problem
		7.5.2 Modified Version of PCP
	7.6 Reducibility
		7.6.1 Properties
		7.6.2 Mapping Reducibility
		7.6.3 Formal Definition of Mapping Reducibility
	7.7 Recursion Theorem
		7.7.1 Applications and Uses of Recursion
	7.8 Rice’s Theorem
	7.9 Ackermann’s Function
	Solved Problems
	Summary
	Short Answers
	Fill in the Blanks
	Objective Question Bank
	Exercises
8. Non-deterministic Polynomial Completeness
	8.1 NP-hard and NP-complete
		8.1.1 Classification of Problems
	8.2 P Problems
	8.3 NP Problems
	8.4 Tractable Problems
	8.5 NP-complete
	8.6 NP-hard
	8.7 Examples of Problems in Different Classes
	8.8 NP-completeness
	8.9 Reduction
		8.9.1 Computational Complexity
		8.9.2 0–1 Knapsack Problem
		8.9.3 Computational Complexity
	Solved Problems
	Summary
	Short Answers
	Fill in the Blanks
	Objective Question Bank
	Exercises
9. LR(k) and LL(1) Grammars
	9.1 LL(1) Grammar
	9.2 Rules for Verifying Whether the Given Grammar Is LL(1) or Not
	9.3 LR(K) Grammars
	9.4 Properties of LR(k) Grammars
	9.5 Construction of LR(0) Items for Context Free Grammars
	9.6 Definition of LR(0) Grammar
	9.7 LR(1) Grammar
	Solved Problems
	Summary
	Short Answers
	Fill in the Blanks
	Objective Question Bank
	Exercises
Appendix A: Proposition and Predicate Logic
	A.1 Propositions
	A.2 Connectives
	A.3 Well-Formed Formula
		A.3.1 Truth Table for a Well-formed Formula
	A.4 Logical Identities
	A.5 Normal Forms of Well-formed Formals
		A.5.1 Construction to Obtain a Disjunctive Normal Form of a Given Formula
	A.6 Principal Disjunctive Normal Form
		A.6.1 Construction to Obtain the Principal Disjunctive Normal Form of a Given Formula
	A.7 Predicate Calculus
	A.9 Well-formed Formulas of Predicate Calculus
	A.8 Universal and Existential Quantifier
	A.10 Rules of Inference for Predicate Calculus
	Summary
Appendix B: Frequently Asked University Questions with Solutions
	Part A - Brief Questions —
	Part B - Detailed Questions —
References
Index