Learn · NPTEL

Course10610402842 lectures

Theory of Computation

Prof. Somenath Biswas · IIT Kanpur

Start with lecture 1 At NPTEL

Lectures

Theory of Computation

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

Syllabus and materials

At NPTEL, as the course publishes them.

Credits and licence

Institution
IIT Kanpur
Department
Computer Science and Engineering
Teacher
Prof. Somenath Biswas
Level
Undergraduate
Language
English
Subjects
Computer science, Engineering
Source
NPTEL
Licence
CC BY-NC-SA, as NPTEL states it. Non-commercial use only. NPTEL's terms
Attribution
NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
Who can watch
NPTEL gives no rating. Invisible Network shows it to Tweens profiles and older, judged from what the source says about it. How courses are placed