Formal Languages and Automata Theory


Lecture 1 - Introduction


Lecture 2 - Alphabet, Strings, Languages


Lecture 3 - Finite Representation


Lecture 4 - Grammars (CFG)


Lecture 5 - Derivation Trees


Lecture 6 - Regular Grammars


Lecture 7 - Finite Automata


Lecture 8 - Nondeterministic Finite Automata


Lecture 9 - NFA <=> DFA


Lecture 10 - Myhill-Nerode Theorem


Lecture 11 - Minimization


Lecture 12 - RE => FA


Lecture 13 - FA => RE


Lecture 14 - FA <=> RG


Lecture 15 - Variants of FA


Lecture 16 - Closure Properties of RL


Lecture 17 - Homomorphism


Lecture 18 - Pumping Lemma


Lecture 19 - Simplification of CFG


Lecture 20 - Normal Forms of CFG


Lecture 21 - Properties of CFLs


Lecture 22 - Pushdown Automata


Lecture 23 - PDA <=> CFG


Lecture 24 - Turing Machines


Lecture 25 - Turing Computable Functions


Lecture 26 - Combining Turing Machines


Lecture 27 - Multi Input


Lecture 28 - Turing Decidable Languages


Lecture 29 - Varients of Turing Machines


Lecture 30 - Structured Grammars


Lecture 31 - Decidability


Lecture 32 - Undecidability 1


Lecture 33 - Undecidability 2


Lecture 34 - Undecidability 3


Lecture 35 - Time Bounded Turing Machines


Lecture 36 - P and NP


Lecture 37 - NP-Completeness


Lecture 38 - NP-Complete Problems 1


Lecture 39 - NP-Complete Problems 2


Lecture 40 - NP-Complete Problems 3


Lecture 41 - Chomsky Hierarchy