Theory of Computation

Theory of Computation

nptelhrd via YouTube Direct link

Mod-01 Lec-01 What is theory of computation?

1 of 42

1 of 42

Mod-01 Lec-01 What is theory of computation?

Class Central Classrooms beta

YouTube playlists curated by Class Central.

Classroom Contents

Theory of Computation

Automatically move to the next video in the Classroom when playback concludes

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

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.