Formal languages 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 Functions1.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â#x80;#x93;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 â#x80;#x98;câ#x80;#x99;; 2.1.3 Transition Diagram.

2.1.4 Transition Table2.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)â#x80;#x94;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 FA2.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 Expressions3.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â#x80;#x99;s Theorem; 3.6.2 Ardenâ#x80;#x99;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.