NOC:Theory of Computation


Lecture 1 - Introduction to Finite Automata


Lecture 2 - Basic Notation and Convention, DFA Edit Lesson


Lecture 3 - Example of DFAs


Lecture 4 - Computation by DFA and Regular operation


Lecture 5 - Introduction to Nondeterminism


Lecture 6 - NFA, definition and examples


Lecture 7 - Equivalence of NFA and DFA, Closure properties


Lecture 8 - Regular expressions


Lecture 9 - Algebraic properties, RE to NFA conversion


Lecture 10 - GNFA to RE conversion


Lecture 11 - More closure properties of regular languages


Lecture 12 - Non-regular languages and pumping lemma


Lecture 13 - Examples of non-regular languages


Lecture 14 - DFA minimization


Lecture 15 - Introduction to CFGs


Lecture 16 - Examples of CFGs, Reg subset of CFL


Lecture 17 - Parse tree, derivation, ambiguity


Lecture 18 - Normal forms, Chomsky normal form


Lecture 19 - Non-CFLs, pumping lemma


Lecture 20 - Examples of non- CFLs


Lecture 21 - Pushdown Automata


Lecture 22 - Pushdown Automata - Definition and Example


Lecture 23 - Pushdown Automata - Examples and Relation with CFGs


Lecture 24 - Closure Properties of CFLs


Lecture 25 - Deterministic Context Free Languages


Lecture 26 - Turing Machine


Lecture 27 - More on Turing Machine


Lecture 28 - Non deterministic Turing Machine Edit Lesson


Lecture 29 - Configuration Graphs


Lecture 30 - Closure Properties of Decidable and Turing recognizable languages


Lecture 31 - Decidability properties of Regular and Context Free Languages


Lecture 32 - Undecidability


Lecture 33 - More on Undecidability


Lecture 34 - Reduction


Lecture 35 - Applications of Reduction


Lecture 36 - Rice's theorem


Lecture 37 - Introduction to Computational Complexity Theory


Lecture 38 - More on the class NP


Lecture 39 - NP-Completeness


Lecture 40 - More on NP-Completeness