# Theory of Computation

- Institution: IIT Kanpur
- Department: Computer Science and Engineering
- Teacher: Prof. Somenath Biswas
- Level: Undergraduate
- Language: English
- Subjects: Computer science, Engineering
- Source: [NPTEL](https://nptel.ac.in/courses/106104028)
- Licence: [CC BY-NC-SA](https://nptel.ac.in/faq) (Non-commercial use only.)
- Syllabus: [at the source](https://nptel.ac.in/courses/106104028)
- Who can watch: Tweens profiles and older (sources give no ratings; placed by Invisible Network from the source's own words)

## Lectures

1. [Lecture-01 What is theory of computation? Set membership problem, basic notions like alphabet, strings, formal languages.](https://invisiblenetwork.ai/learn/nptel/106104028/9155f2dab6f7) (Video)
2. [Lecture-02-Introduction to finite automaton.](https://invisiblenetwork.ai/learn/nptel/106104028/55909aececab) (Video)
3. [Lecture-03-Finite automata continued, deterministic finite automata(DFAs), language accepted by a DFA.](https://invisiblenetwork.ai/learn/nptel/106104028/5bd895ef4e17) (Video)
4. [Lecture-04-Regular languages, their closure properties.](https://invisiblenetwork.ai/learn/nptel/106104028/27e5bdcde797) (Video)
5. [Lecture-05-DFAs solve set membership problems in linear time, pumping lemma.](https://invisiblenetwork.ai/learn/nptel/106104028/896ecdc906a6) (Video)
6. [Lecture-06-More examples of nonregular languages, proof of pumping lemma, pumping lemma as a game, converse of pumping lemma does not hold.](https://invisiblenetwork.ai/learn/nptel/106104028/7937a0394636) (Video)
7. [Lecture-07-A generalization of pumping lemma, nondeterministic finite automata (NFAs), computation trees for NFAs.](https://invisiblenetwork.ai/learn/nptel/106104028/e0881867642f) (Video)
8. [Lecture-08-Formal description of NFA, language accepted by NFA, such languages are also regular.](https://invisiblenetwork.ai/learn/nptel/106104028/49ae1efa664f) (Video)
9. [Lecture-09-'Guess and verify' paradigm for nondeterminism.](https://invisiblenetwork.ai/learn/nptel/106104028/34347f144b82) (Video)
10. [Lecture-10-NFA's with epsilon transitions.](https://invisiblenetwork.ai/learn/nptel/106104028/8d9b57c1ef99) (Video)
11. [Lecture-11-Regular expressions, they denote regular languages.](https://invisiblenetwork.ai/learn/nptel/106104028/61a9801f140c) (Video)
12. [Lecture-12-Construction of a regular expression for a language given a DFA accepting it. Algebraic closure properies of regular languages.](https://invisiblenetwork.ai/learn/nptel/106104028/7ffad927cfba) (Video)
13. [Lecture-13-Closure properties continued.](https://invisiblenetwork.ai/learn/nptel/106104028/38797f9f4f50) (Video)
14. [Lecture-14-Closure under reversal, use of closure properties.](https://invisiblenetwork.ai/learn/nptel/106104028/fa3a249f5ab9) (Video)
15. [Lecture-15-Decision problems for regular languages.](https://invisiblenetwork.ai/learn/nptel/106104028/7146e3157638) (Video)
16. [Lecture-16-About minimization of states of DFAs. Myhill-Nerode theorem.](https://invisiblenetwork.ai/learn/nptel/106104028/826bb17438c5) (Video)
17. [Lecture-17-Continuation of proof of Myhill-Nerode theorem.](https://invisiblenetwork.ai/learn/nptel/106104028/9b0fda8a164d) (Video)
18. [Lecture-18-Application of Myhill-Nerode theorem. DFA minimization.](https://invisiblenetwork.ai/learn/nptel/106104028/980d09f88dd9) (Video)
19. [Lecture-19-DFA minimization continued.](https://invisiblenetwork.ai/learn/nptel/106104028/260483c1d29c) (Video)
20. [Lecture-20-Introduction to context free languages (cfls) and context free grammars (cfgs). Derivation of strings by cfgs.](https://invisiblenetwork.ai/learn/nptel/106104028/e2c4f61a954f) (Video)
21. [Lecture-21-Languages generated by a cfg, leftmost derivation, more examples of cfgs and cfls.](https://invisiblenetwork.ai/learn/nptel/106104028/13af90a6f633) (Video)
22. [Lecture-22-Parse trees, inductive proof that L is L(G). All regular languages are context free.](https://invisiblenetwork.ai/learn/nptel/106104028/f954eb460ca2) (Video)
23. [Lecture-23-Towards Chomsky normal forms: elimination of useless symbols, analysis of reachable symbols, generating nonterminals, order of substeps matter.](https://invisiblenetwork.ai/learn/nptel/106104028/f5fe82e49c5c) (Video)
24. [Lecture-24-Simplification of cfgs continued, Removal of epsilon productions: algorithm and its correctness.](https://invisiblenetwork.ai/learn/nptel/106104028/d32f7c47eb27) (Video)
25. [Lecture-25-Elimination of unit productions. Converting a cfg into Chomsky normal form. Towards pumping lemma for cfls](https://invisiblenetwork.ai/learn/nptel/106104028/df99c8670fa4) (Video)
26. [Lecture-26-Pumping lemma for cfls. Adversarial paradigm.](https://invisiblenetwork.ai/learn/nptel/106104028/e8544d5ffa0d) (Video)
27. [Lecture-27-Completion of pumping lemma proof. Examples of use of pumping lemma. Converse of lemma does not hold. Closure properties of cfls.](https://invisiblenetwork.ai/learn/nptel/106104028/fb2714ad63b7) (Video)
28. [Lecture-28-Closure properties continued. cfls not closed under complementation.](https://invisiblenetwork.ai/learn/nptel/106104028/7014f355a01d) (Video)
29. [Lecture-29-Another example of a cfl whose complement is not a cfl. Decision problems for cfls.](https://invisiblenetwork.ai/learn/nptel/106104028/6ace28800f53) (Video)
30. [Lecture-30-More decision problems. CYK algorithm for membership decision.](https://invisiblenetwork.ai/learn/nptel/106104028/2142576a01fa) (Video)
31. [Lecture-31-Introduction to pushdown automata (pda).](https://invisiblenetwork.ai/learn/nptel/106104028/e1863086fce8) (Video)
32. [Lecture-32-pda configurations, acceptance notions for pdas. Transition diagrams for pdas](https://invisiblenetwork.ai/learn/nptel/106104028/753f7f3c8015) (Video)
33. [Lecture-33-Equivalence of acceptance by empty stack and acceptance by final state.](https://invisiblenetwork.ai/learn/nptel/106104028/f0592cfbb3e4) (Video)
34. [Lecture-34-Turing machines (TM): motivation, informal definition, example, transition diagram.](https://invisiblenetwork.ai/learn/nptel/106104028/7b1792905461) (Video)
35. [Lecture-35-Execution trace, another example (unary to binary conversion).](https://invisiblenetwork.ai/learn/nptel/106104028/2858d21529be) (Video)
36. [Lecture-36-Example continued. Finiteness of TM description, TM configuration, language acceptance, definition of recursively enumerable (r.e.) languages.](https://invisiblenetwork.ai/learn/nptel/106104028/35e9c9279886) (Video)
37. [Lecture-37-Notion of non-acceptance or rejection of a string by a TM. Multitrack TM, its equivalence to standard TM. Multitape TMs.](https://invisiblenetwork.ai/learn/nptel/106104028/0531b06cdf45) (Video)
38. [Lecture-38-Simulation of multitape TMs by basic model. Nondeterministic TM (NDTM). Equivalence of NDTMs with deterministic TMs.](https://invisiblenetwork.ai/learn/nptel/106104028/31297a2e31c8) (Video)
39. [Lecture-39-Counter machines and their equivalence to basic TM model.](https://invisiblenetwork.ai/learn/nptel/106104028/dbc6f67c1fc4) (Video)
40. [Lecture-40-TMs can simulate computers, diagonalization proof.](https://invisiblenetwork.ai/learn/nptel/106104028/b5f74b91828a) (Video)
41. [Lecture-41-Existence of non-r.e. languages, recursive languages, notion of decidability.](https://invisiblenetwork.ai/learn/nptel/106104028/75394a310fd0) (Video)
42. [Lecture-42-Separation of recursive and r.e. classes, halting problem and its undecidability.](https://invisiblenetwork.ai/learn/nptel/106104028/650573a91611) (Video)