Formal Language and Automata Theory

Description

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