Media Storage Type : 32 GB USB Stick
NPTEL Subject Matter Expert : Prof. Somenath Biswas
NPTEL Co-ordinating Institute : IIT Kanpur
NPTEL Lecture Count : 42
NPTEL Course Size : 20 GB
NPTEL PDF Text Transcription : Available and Included
NPTEL Subtitle Transcription : Available and Included (SRT)
Lecture Titles:
Lecture 1 - What is theory of computation? Set membership problem, basic notions like alphabet, strings, formal languages
Lecture 2 - Introduction to finite automaton
Lecture 3 - Finite automata continued, deterministic finite automata(DFAs), language accepted by a DFA
Lecture 4 - Regular languages, their closure properties
Lecture 5 - DFAs solve set membership problems in linear time, pumping lemma
Lecture 6 - More examples of nonregular languages, proof of pumping lemma, pumping lemma as a game, converse of pumping lemma does not hold
Lecture 7 - A generalization of pumping lemma, nondeterministic finite automata (NFAs), computation trees for NFAs
Lecture 8 - Formal description of NFA, language accepted by NFA, such languages are also regular
Lecture 9 - 'Guess and verify' paradigm for nondeterminism
Lecture 10 - NFA's with epsilon transitions
Lecture 11 - Regular expressions, they denote regular languages
Lecture 12 - Construction of a regular expression for a language given a DFA accepting it. Algebraic closure properies of regular languages
Lecture 13 - Closure properties (Continued...)
Lecture 14 - Closure under reversal, use of closure properties
Lecture 15 - Decision problems for regular languages
Lecture 16 - About minimization of states of DFAs. Myhill-Nerode theorem
Lecture 17 - Continuation of proof of Myhill-Nerode theorem
Lecture 18 - Application of Myhill-Nerode theorem. DFA minimization
Lecture 19 - DFA minimization (Continued...)
Lecture 20 - Introduction to context free languages (cfls) and context free grammars (cfgs). Derivation of strings by cfgs
Lecture 21 - Languages generated by a cfg, leftmost derivation, more examples of cfgs and cfls
Lecture 22 - Parse trees, inductive proof that L is L(G). All regular languages are context free
Lecture 23 - Towards Chomsky normal forms: elimination of useless symbols, analysis of reachable symbols, generating nonterminals, order of substeps matter
Lecture 24 - Simplification of cfgs continued, Removal of epsilon productions: algorithm and its correctness
Lecture 25 - Elimination of unit productions. Converting a cfg into Chomsky normal form. Towards pumping lemma for cfls
Lecture 26 - Pumping lemma for cfls. Adversarial paradigm
Lecture 27 - Completion of pumping lemma proof. Examples of use of pumping lemma. Converse of lemma does not hold. Closure properties of cfls
Lecture 28 - Closure properties continued. cfls not closed under complementation
Lecture 29 - Another example of a cfl whose complement is not a cfl. Decision problems for cfls
Lecture 30 - More decision problems. CYK algorithm for membership decision
Lecture 31 - Introduction to pushdown automata (pda)
Lecture 32 - pda configurations, acceptance notions for pdas. Transition diagrams for pdas
Lecture 33 - Equivalence of acceptance by empty stack and acceptance by final state
Lecture 34 - Turing machines (TM): motivation, informal definition, example, transition diagram
Lecture 35 - Execution trace, another example (unary to binary conversion)
Lecture 36 - Example continued. Finiteness of TM description, TM configuration, language acceptance, definition of recursively enumerable (r.e.) languages
Lecture 37 - Notion of non-acceptance or rejection of a string by a TM. Multitrack TM, its equivalence to standard TM. Multitape TMs
Lecture 38 - Simulation of multitape TMs by basic model. Nondeterministic TM (NDTM). Equivalence of NDTMs with deterministic TMs
Lecture 39 - Counter machines and their equivalence to basic TM model
Lecture 40 - TMs can simulate computers, diagonalization proof
Lecture 41 - Existence of non-r.e. languages, recursive languages, notion of decidability
Lecture 42 - Separation of recursive and r.e. classes, halting problem and its undecidability