Theory of Automata, Formal Languages and Computation


Lecture 1 - Grammars and Natural Language Processing


Lecture 2 - Grammars and Languages Generated


Lecture 3 - Grammars and Languages Generated (Continued.)


Lecture 4 - Ambiguity in CFG


Lecture 5 - Simplication of CFG


Lecture 6 - Removal of Unit Productions, Chomsky Normal Form for CFG


Lecture 7 - Greibach Normal Form for CFG


Lecture 8 - Final State Automata


Lecture 9 - Non Deterministic FSA


Lecture 10 - Non Deterministic FSA (Continued.)


Lecture 11 - Non Deterministic FSA with E(Epsilon)- Moves


Lecture 12 - Equivalence Between FSA and Type 3 Grammars


Lecture 13 - Regular Expressions, Regular Expressions to NFSA


Lecture 14 - DFSA to Regular Expressions


Lecture 15 - Problems and Solutions - I


Lecture 16 - Pumping Lemmas for Regular Sets and CFL


Lecture 17 - MYHILL - Nerode Theorem


Lecture 18 - Minimization of DFSA


Lecture 19 - FSA with output Moore and Mealy Machines


Lecture 20 - Pushdown Automata


Lecture 21 - Pushdown Automata, Equivalence Between Acceptance by Empty Store and Acceptance by Final State


Lecture 22 - Pushdown Automata CFG to PDA


Lecture 23 - Pushdown Automata PDA to CFG


Lecture 24 - Problems and Solutions - II


Lecture 25 - Problems and Solutions - III


Lecture 26 - Turing Machines


Lecture 27 - Turing Machines (Continued.)


Lecture 28 - Turing Machine as Acceptor, Techniques for TM Construction


Lecture 29 - Generalized Versions of Turing Machines


Lecture 30 - Turing Machine as a Generating Device


Lecture 31 - Recursive Sets, Recursively Innumerable Sets, Encoding of TM, Halting Problem


Lecture 32 - Problems and Instances, Universal TM, Decidability


Lecture 33 - RICE'S Theorem, Linear Bounded Automata, Properties of TM


Lecture 34 - POST'S Correspondence Problems


Lecture 35 - POST'S Correspondence Problems (Continued.), Time and Tape Complexity of TM


Lecture 36 - NP - Complete Problems, Cook's Theorem


Lecture 37 - NP - Complete Problems (Continued.)


Lecture 38 - Regulated Rewriting


Lecture 39 - L-Systems


Lecture 40 - Grammar Systems


Lecture 41 - DNA Computing


Lecture 42 - Membrane Computing