Learn · Theory of Computation

Lecture 5 of 42Theory of Computation

Lecture-05-DFAs solve set membership problems in linear time, pumping lemma.

Prof. Somenath Biswas · IIT Kanpur

Credits and licence

From
Theory of Computation, IIT Kanpur (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.
Who can watch
Tweens profiles and older. How courses are placed

All the lectures

  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