# Theory of Automata

Theory of Automata
(CS402)
Lecture N0. 1 .......................................................................................................................................................... 4
Summary............................................................................................................................................................ 4
What does automata mean? ............................................................................................................................... 4
Introduction to languages................................................................................................................................... 4
Alphabets ........................................................................................................................................................... 4
Strings ................................................................................................................................................................ 4
Defining Languages........................................................................................................................................... 5
Lecture N0. 2 .......................................................................................................................................................... 9
Summary............................................................................................................................................................ 9
Kleene Star Closure ........................................................................................................................................... 9
Recursive definition of languages...................................................................................................................... 9
Lecture N0. 3 ........................................................................................................................................................ 11
Summary.......................................................................................................................................................... 11
Regular Expression .......................................................................................................................................... 11
Recursive definition of Regular Expression(RE)............................................................................................. 11
Method 3 (Regular Expressions) ..................................................................................................................... 11
Lecture N0. 4 ........................................................................................................................................................ 12
Equivalent Regular Expressions ...................................................................................................................... 12
Method 4 (Finite Automaton) .......................................................................................................................... 13
Lecture N0. 5 ........................................................................................................................................................ 15
Lecture N0. 6 ........................................................................................................................................................ 17
Equivalent FAs ................................................................................................................................................ 17
Lecture N0. 7 ........................................................................................................................................................ 20
FA corresponding to finite languages .............................................................................................................. 20
Method 5 (Transition Graph) ........................................................................................................................... 22
Lecture N0. 8 ........................................................................................................................................................ 23
Examples of TGs: accepting all strings, accepting none, starting with b, not ending in b, containing aa,
containing aa or bb........................................................................................................................................... 23
Lecture N0. 9 ........................................................................................................................................................ 25
Generalized Transition Graphs ........................................................................................................................ 27
Lecture N0. 10 ...................................................................................................................................................... 28
Nondeterminism............................................................................................................................................... 29
Kleene's Theorem............................................................................................................................................ 29
Lecture N0. 11 ...................................................................................................................................................... 30
Proof(Kleene's Theorem Part II) ..................................................................................................................... 30
Lecture N0. 12 ...................................................................................................................................................... 34
Kleene's Theorem Part III ............................................................................................................................... 35
Lecture N0. 13 ...................................................................................................................................................... 38
Lecture N0. 14 ...................................................................................................................................................... 41
Lecture N0. 15 ...................................................................................................................................................... 44
Nondeterministic Finite Automaton (NFA) .................................................................................................... 44
Converting an FA to an equivalent NFA ......................................................................................................... 45
Lecture N0. 16 ...................................................................................................................................................... 47
NFA with Null String ...................................................................................................................................... 47
Lecture N0. 17 ...................................................................................................................................................... 50
NFA and Kleene's Theorem ............................................................................................................................ 50
Lecture N0. 18 ...................................................................................................................................................... 53
NFA corresponding to Concatenation of FAs.................................................................................................. 53
NFA corresponding to the Closure of an FA ................................................................................................... 55
Lecture N0. 19 ...................................................................................................................................................... 57
Memory required to recognize a language....................................................................................................... 57
Distinguishable strings and Indistinguishable strings ...................................................................................... 58
Lecture N0. 20 ...................................................................................................................................................... 60
Finite Automaton with output .......................................................................................................................... 60
Moore machine ................................................................................................................................................ 60
Lecture N0. 21 ...................................................................................................................................................... 62
Mealy machine................................................................................................................................................. 62
Lecture N0. 22 ...................................................................................................................................................... 65
2
Theory of Automata
(CS402)
Equivalent machines ........................................................................................................................................ 65
Lecture N0. 23 ...................................................................................................................................................... 68
Lecture N0. 24 ...................................................................................................................................................... 70
Regular languages............................................................................................................................................ 70
Complement of a language .............................................................................................................................. 71
Lecture N0. 25 ...................................................................................................................................................... 73
Nonregular languages ...................................................................................................................................... 76
Lecture N0. 26 ...................................................................................................................................................... 77
Pumping Lemma.............................................................................................................................................. 77
Lecture N0. 27 ...................................................................................................................................................... 80
Pumping Lemma version II ............................................................................................................................. 80
Lecture N0. 28 ...................................................................................................................................................... 82
Pseudo theorem................................................................................................................................................ 83
Lecture N0. 29 ...................................................................................................................................................... 84
Decidability...................................................................................................................................................... 84
Determining whether the two languages are equivalent or not ? ..................................................................... 85
Lecture N0. 30 ...................................................................................................................................................... 88
Lecture N0. 31 ...................................................................................................................................................... 92
Context Free Grammar (CFG) ......................................................................................................................... 92
CFG terminologies........................................................................................................................................... 92
Lecture N0. 32 ...................................................................................................................................................... 95
Trees ................................................................................................................................................................ 96
Lecture N0. 33 ...................................................................................................................................................... 98
Polish Notation (o-o-o) .................................................................................................................................... 99
Lecture N0. 34 .................................................................................................................................................... 101
Total language tree......................................................................................................................................... 101
Regular Grammar .......................................................................................................................................... 102
Lecture N0. 35 .................................................................................................................................................... 104
Null Production.............................................................................................................................................. 104
Lecture N0. 36 .................................................................................................................................................... 107
Chomsky Normal Form (CNF) ...................................................................................................................... 107
Lecture N0. 37 .................................................................................................................................................... 110
A new format for FAs .................................................................................................................................... 110
Lecture N0. 38 .................................................................................................................................................... 114
Nondeterministic PDA................................................................................................................................... 116
Lecture N0. 39 .................................................................................................................................................... 119
PDA corresponding to CFG........................................................................................................................... 119
Lecture N0. 40 .................................................................................................................................................... 123
Conversion form of PDA ............................................................................................................................... 124
Lecture N0. 41 .................................................................................................................................................... 126
Lecture N0. 42 .................................................................................................................................................... 129
Lecture N0. 43 .................................................................................................................................................... 132
Non-Context-Free language........................................................................................................................... 132
Pumping lemma for CFLs.............................................................................................................................. 133
Lecture N0. 44 .................................................................................................................................................... 139
Decidablity..................................................................................................................................................... 139
Parsing Techniques ........................................................................................................................................ 142
Lecture N0. 45 .................................................................................................................................................... 147
Turing machine .............................................................................................................................................. 147
3