Contents
1 Mathematical Preliminaries 3
2 Formal Languages 4
2.1 Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4 Finite Representation . . . . . . . . . . . . . . . . . . . . . . . 13
2.4.1 Regular Expressions . . . . . . . . . . . . . . . . . . . 13
3 Grammars 18
3.1 Context-Free Grammars . . . . . . . . . . . . . . . . . . . . . 19
3.2 Derivation Trees . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.2.1 Ambiguity . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.3 Regular Grammars . . . . . . . . . . . . . . . . . . . . . . . . 32
3.4 Digraph Representation . . . . . . . . . . . . . . . . . . . . . 36
4 Finite Automata 38
4.1 Deterministic Finite Automata . . . . . . . . . . . . . . . . . 39
4.2 Nondeterministic Finite Automata . . . . . . . . . . . . . . . 49
4.3 Equivalence of NFA and DFA . . . . . . . . . . . . . . . . . . 54
4.3.1 Heuristics to Convert NFA to DFA . . . . . . . . . . . 58
4.4 Minimization of DFA . . . . . . . . . . . . . . . . . . . . . . . 61
4.4.1 Myhill-Nerode Theorem . . . . . . . . . . . . . . . . . 61
4.4.2 Algorithmic Procedure for Minimization . . . . . . . . 65
4.5 Regular Languages . . . . . . . . . . . . . . . . . . . . . . . . 72
4.5.1 Equivalence of Finite Automata and Regular Languages 72
4.5.2 Equivalence of Finite Automata and Regular Grammars 84
4.6 Variants of Finite Automata . . . . . . . . . . . . . . . . . . . 89
4.6.1 Two-way Finite Automaton . . . . . . . . . . . . . . . 89
4.6.2 Mealy Machines . . . . . . . . . . . . . . . . . . . . . . 91
5 Properties of Regular Languages 94
5.1 Closure Properties . . . . . . . . . . . . . . . . . . . . . . . . 94
5.1.1 Set Theoretic Properties . . . . . . . . . . . . . . . . . 94
5.1.2 Other Properties . . . . . . . . . . . . . . . . . . . . . 97
5.2 Pumping Lemma . . . . . . . . . . . . . . . . . . . . . . . . . 104
Formal Languages and Automata Theory
D. Goswami and K. V. Krishna
Source : https://www.iitg.ernet.in/dgoswami/Flat-Notes.pdf
