CS402 all Video Lectures compress file Download on one click
Lecture N0. 1 ……………………………………………………………………………………………………………..5
Summary………………………………………………………………………………………………………………..5
What does automata mean? ………………………………………………………………………………………5
Introduction to languages………………………………………………………………………………………….5
Alphabets ……………………………………………………………………………………………………………….5
Strings ……………………………………………………………………………………………………………………5
Defining Languages…………………………………………………………………………………………………6
Lecture N0. 2 ……………………………………………………………………………………………………………10
Summary………………………………………………………………………………………………………………10
Kleene Star Closure ……………………………………………………………………………………………….10
Recursive definition of languages…………………………………………………………………………….10
Lecture N0. 3 ……………………………………………………………………………………………………………12
Summary………………………………………………………………………………………………………………12
Regular Expression ………………………………………………………………………………………………..12
Recursive definition of Regular Expression(RE) ……………………………………………………….12
Method 3 (Regular Expressions) ……………………………………………………………………………..12
Lecture N0. 4 ……………………………………………………………………………………………………………13
Equivalent Regular Expressions ………………………………………………………………………………13
Method 4 (Finite Automaton) ………………………………………………………………………………….14
Lecture N0. 5 ……………………………………………………………………………………………………………16
Lecture N0. 6 ……………………………………………………………………………………………………………18
Equivalent FAs………………………………………………………………………………………………………18
Lecture N0. 7 ……………………………………………………………………………………………………………21
FA corresponding to finite languages……………………………………………………………………….21
Method 5 (Transition Graph)…………………………………………………………………………………..23
Lecture N0. 8 ……………………………………………………………………………………………………………24
Examples of TGs: accepting all strings, accepting none, starting with b, not ending in b,
containing aa, containing aa or bb ……………………………………………………………………………24
Lecture N0. 9 ……………………………………………………………………………………………………………26
Generalized Transition Graphs ………………………………………………………………………………..28
Lecture N0. 10 ………………………………………………………………………………………………………….29
Nondeterminism…………………………………………………………………………………………………….30
Kleene’s Theorem………………………………………………………………………………………………….30
Lecture N0. 11 ………………………………………………………………………………………………………….31
Proof(Kleene’s Theorem Part II) ……………………………………………………………………………..31
Lecture N0. 12 ………………………………………………………………………………………………………….35
Kleene’s Theorem Part III ………………………………………………………………………………………36
Lecture N0. 13 ………………………………………………………………………………………………………….39
Lecture N0. 14 ………………………………………………………………………………………………………….42
Lecture N0. 15 ………………………………………………………………………………………………………….45
Nondeterministic Finite Automaton (NFA)………………………………………………………………45
Converting an FA to an equivalent NFA …………………………………………………………………..46
Lecture N0. 16 ………………………………………………………………………………………………………….48
NFA with Null String……………………………………………………………………………………………..48
Lecture N0. 17 ………………………………………………………………………………………………………….51
NFA and Kleene’s Theorem ……………………………………………………………………………………51
Lecture N0. 18 ………………………………………………………………………………………………………….54
NFA corresponding to Concatenation of FAs ……………………………………………………………54
NFA corresponding to the Closure of an FA……………………………………………………………..56
Lecture N0. 19 ………………………………………………………………………………………………………….58
Memory required to recognize a language…………………………………………………………………58
Distinguishable strings and Indistinguishable strings………………………………………………….59
Lecture N0. 20 ………………………………………………………………………………………………………….61
Finite Automaton with output………………………………………………………………………………….61
Moore machine ……………………………………………………………………………………………………..61
Lecture N0. 21 ………………………………………………………………………………………………………….63
Mealy machine………………………………………………………………………………………………………63
Lecture N0. 22 ………………………………………………………………………………………………………….66
Equivalent machines ………………………………………………………………………………………………66
Lecture N0. 23 ………………………………………………………………………………………………………….69
Lecture N0. 24 ………………………………………………………………………………………………………….71
Regular languages………………………………………………………………………………………………….71
Complement of a language ……………………………………………………………………………………..72
Lecture N0. 25 ………………………………………………………………………………………………………….74
Nonregular languages …………………………………………………………………………………………….77
Lecture N0. 26 ………………………………………………………………………………………………………….78
Pumping Lemma……………………………………………………………………………………………………78
Lecture N0. 27 ………………………………………………………………………………………………………….81
Pumping Lemma version II …………………………………………………………………………………….81
Lecture N0. 28 ………………………………………………………………………………………………………….83
Pseudo theorem……………………………………………………………………………………………………..84
Lecture N0. 29 ………………………………………………………………………………………………………….85
Decidability…………………………………………………………………………………………………………..85
Determining whether the two languages are equivalent or not ?…………………………………..86
Lecture N0. 30 ………………………………………………………………………………………………………….89
Lecture N0. 31 ………………………………………………………………………………………………………….93
Context Free Grammar (CFG)…………………………………………………………………………………93
CFG terminologies…………………………………………………………………………………………………93
Lecture N0. 32 ………………………………………………………………………………………………………….96
Trees…………………………………………………………………………………………………………………….97
Lecture N0. 33 ………………………………………………………………………………………………………….99
Polish Notation (o-o-o) …………………………………………………………………………………………100
Lecture N0. 34 ………………………………………………………………………………………………………..102
Total language tree……………………………………………………………………………………………….102
Regular Grammar…………………………………………………………………………………………………103
Lecture N0. 35 ………………………………………………………………………………………………………..106
Null Production……………………………………………………………………………………………………106
Lecture N0. 36 ………………………………………………………………………………………………………..109
Chomsky Normal Form (CNF)………………………………………………………………………………109
Lecture N0. 37 ………………………………………………………………………………………………………..113
A new format for FAs…………………………………………………………………………………………..113
Lecture N0. 38 ………………………………………………………………………………………………………..117
Nondeterministic PDA………………………………………………………………………………………….119
Lecture N0. 39 ………………………………………………………………………………………………………..122
PDA corresponding to CFG…………………………………………………………………………………..122
Lecture N0. 40 ………………………………………………………………………………………………………..126
Conversion form of PDA………………………………………………………………………………………127
Lecture N0. 41 ………………………………………………………………………………………………………..129
Lecture N0. 42 ………………………………………………………………………………………………………..132
Lecture N0. 43 ………………………………………………………………………………………………………..135
Non-Context-Free language…………………………………………………………………………………..135
Pumping lemma for CFLs……………………………………………………………………………………..136
Lecture N0. 44 ………………………………………………………………………………………………………..142
Decidablity………………………………………………………………………………………………………….142
Parsing Techniques ………………………………………………………………………………………………145
Lecture N0. 45 ………………………………………………………………………………………………………..150
Turing machine ……………………………………………………………………………………………………150