Learn · Theory of Computation

Lecture 2 of 70week-01

Notations and Terminology in Theory of Computation

Prof. Subrahmanyam Kalyanasundaram · IIT Hyderabad

Credits and licence

From
Theory of Computation, IIT Hyderabad (at NPTEL)
Licence
CC BY-NC-SA, as NPTEL states it. Non-commercial use only.
Attribution
NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge. Coordinated by IIT Madras.
Who can watch
Tweens profiles and older. How courses are placed

All the lectures

  1. An Introduction to The Theory of Computation Video
  2. Notations and Terminology in Theory of Computation Video
  3. An Introduction to Finite Automata and Regular Languages - Part 01 Video
  4. An Introduction to Finite Automata and Regular Languages - Part 02 Video
  5. Significance of Regular Languages and Regular Operations Video
  6. Closure Properties of Regular Languages Under Union, Concatenation and Kleene Star Operation-Part 01 Video
  7. Closure Properties of Regular Languages Under Union, Concatenation and Kleene Star Operation-Part 02 Video
  8. An Introduction to Non-Deterministic Finite Automata (NFA) Video
  9. Formal Definitions and Examples of Non-Deterministic Finite Automata(NFA) Video
  10. Equivalence of NFA and DFA Video
  11. Closure of Regular Languages Under Regular Operations(Using NFA) Video
  12. Regular Expressions - Part 01 Video
  13. Regular Expressions - Part 02 Video
  14. Proving Equivalence of Regular Expression and DFA Through a GNFA Video
  15. Pumping Lemma for Regular Languages - Part 01 Video
  16. Pumping Lemma for Regular Languages - Part 02 Video
  17. Distinguishability of Strings and Myhill-Nerode Theorem Video
  18. Proving the Myhill-Nerode Theorem Video
  19. An Introduction to Context-Free Languages - Part 01 Video
  20. An Introduction to Context-Free Languages - Part 02 Video
  21. Chomsky Normal Form Video
  22. CYK Algorithm - Part 1 Video
  23. CYK Algorithm - Part 2 (Example) Video
  24. Closure Properties of Context Free Languages Video
  25. An Introduction to Push Down Automata Video
  26. Normalizations in PDA and Intersection of Regular Language & CFL Video
  27. Equivalence of Context Free Grammars and Push Down Automata - Part 01 Video
  28. Equivalence of Context Free Grammars and Push Down Automata - Part 02 Video
  29. Equivalence of Context Free Grammars and Push Down Automata - Part 03 Video
  30. Pumping Lemma for Context Free Languages Video
  31. Examples of Pumping Lemma Usage for Context Free Languages Video
  32. Formal Definition of a Turing Machine Video
  33. Turing Recognizable & Decidable Languages and TM Examples Video
  34. Multitape Turing Machine Video
  35. Non-Deterministic Turing Machines Video
  36. Equivalence of Deterministic and Nondeterministic TM Video
  37. Church-Turing Thesis Video
  38. Decidable Problems Concerning Regular Languages Video
  39. Decidable Problems Concerning Context Free Languages Video
  40. Countability of Sets Video
  41. Proof of Existence of Undecidable Languages Video
  42. Halting Problem Video
  43. Co-Turing Recognizability Video
  44. An Introduction to Mapping Reducibility Video
  45. Examples of Proving Undecidability Using Reductions Video
  46. Rice Theorem Video
  47. Computation Histories Video
  48. The Post Correspondence Problem Video
  49. Checking Ambiguity in CFG is Undecidable Video
  50. Time Complexity - Part 1 Video
  51. Time Complexity - Part 2 Video
  52. Non-Deterministic Polynomial Time - Part 1 Video
  53. Non-Deterministic Polynomial Time - Part 2 Video
  54. Verifiability and NP Video
  55. Polynomial Time Reductions - Part 1 Video
  56. Polynomial Time Reductions - Part 2 Video
  57. NP-Completeness Video
  58. Cook-Levin Theorem Video
  59. Cook-Levin Theorem - Proof and Implications Video
  60. CLIQUE and VERTEX-COVER is NP-Complete Video
  61. HAM-PATH is NP-Complete Video
  62. SUBSET-SUM is NP-Complete Video
  63. Knapsack Problem Video
  64. Integer Linear Program is NP-Complete Video
  65. Space Complexity and its Complexity Classes Video
  66. Logspace Reductions and NL-Completeness Video
  67. Savitch's theorem Video
  68. Results in Space Complexity Video
  69. Summary and Concluding Remarks Video
  70. Live Session 22-04-2025 Video