# Theory of Computation Video Lectures

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

NPTELVideos.com