NPTEL : NOC:Theory of Computation (Computer Science and Engineering)

Co-ordinators : Prof. Raghunath Tewari


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