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