NPTEL : Theory of Automata, Formal Languages and Computation (Computer Science and Engineering)

Co-ordinators : Prof. Kamala Krithivasan


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