Media Storage Type : 32 GB USB Stick
NPTEL Subject Matter Expert : Prof. Raghunath Tewari
NPTEL Co-ordinating Institute : IIT Kanpur
NPTEL Lecture Count : 40
NPTEL Course Size : 3.7 GB
NPTEL PDF Text Transcription : Available and Included
NPTEL Subtitle Transcription : Available and Included (SRT)
Lecture Titles:
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