+ Add to collection

CURATOR

EXTRAS

  • Lifetime access. No limits!
  • Mobile accessibility
  • Add to wishlist

Computer Science - Theory of Computation

+ Add to collection
Self-Study Content
  1. Mod-01 Lec-01 What is theory of computation?

    Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For mor

  2. Mod-01 Lec-02 Introduction to finite automaton.

    Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For mor

  3. Mod-01 Lec-03 Finite automata continued, deterministic finite automata(DFAs),

    Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For mor

  4. Mod-01 Lec-04 Regular languages, their closure properties.

    Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For mor

  5. Mod-01 Lec-05 DFAs solve set membership problems in linear time, pumping lemma.

    Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For mor

  6. Mod-01 Lec-06 More examples of nonregular languages, proof of pumping lemma

    Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For mor

  7. Mod-01 Lec-07 A generalization of pumping lemma, nondeterministic finite automata (NFAs)

    Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For mor

  8. Mod-01 Lec-08 Formal description of NFA, language accepted by NFA, such languages are also regular.

    Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For mor

  9. Mod-01 Lec-09 'Guess and verify' paradigm for nondeterminism.

    Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For mor

  10. Mod- 01 Lec-10 NFA's with epsilon transitions.

    Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For mor

  11. Mod-01 Lec-11 Regular expressions, they denote regular languages.

    Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For mor

  12. Mod-01 Lec-12 Construction of a regular expression for a language given a DFA accepting it.

    Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For mor

  13. Mod-01 Lec-13 Closure properties continued.

    Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For mor

  14. Mod-01 Lec-14 Closure under reversal, use of closure properties.

    Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For mor

  15. Mod-01 Lec-15 Decision problems for regular languages.

    Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For mor

  16. Mod-01 Lec-16 About minimization of states of DFAs. Myhill-Nerode theorem.

    Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For mor

  17. Mod-01 Lec-17 Continuation of proof of Myhill-Nerode theorem.

    Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For mor

  18. Mod-01 Lec-18 Application of Myhill-Nerode theorem. DFA minimization.

    Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For mor

  19. Mod-01 Lec-19 DFA minimization continued.

    Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For mor

  20. Mod-01 Lec-20 Introduction to context free languages (cfls)

    Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For mor

  21. Mod-01 Lec-21 Languages generated by a cfg, leftmost derivation, more examples of cfgs and cfls.

    Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For mor

  22. Mod-01 Lec-22 Parse trees, inductive proof that L is L(G). All regular languages are context free.

    Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For mor

  23. Mod-01 Lec-23 Towards Chomsky normal forms: elimination of useless symbols

    Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For mor

  24. Mod-01 Lec-24 Simplification of cfgs continued, Removal of epsilon productions

    Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For mor

  25. Mod-01 Lec-25 Elimination of unit productions. Converting a cfg into Chomsky normal form.

    Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For mor

  26. Mod-01 Lec-26 Pumping lemma for cfls. Adversarial paradigm.

    Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For mor

  27. Mod-01 Lec-27 Completion of pumping lemma proof

    Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For mor

  28. Mod-01 Lec-28 Closure properties continued. cfls not closed under complementation.

    Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For mor

  29. Mod-01 Lec-29 Another example of a cfl whose complement is not a cfl. Decision problems for cfls.

    Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For mor

  30. Mod-01 Lec-30 More decision problems. CYK algorithm for membership decision.

    Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For mor

  31. Mod-01 Lec-31 Introduction to pushdown automata (pda).

    Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For mor

  32. Mod-01 Lec-32 pda configurations, acceptance notions for pdas. Transition diagrams for pdas

    Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For mor

  33. Mod-01 Lec-33 Equivalence of acceptance by empty stack and acceptance by final state.

    Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For mor

  34. Mod-01 Lec-34 Turing machines (TM): motivation, informal definition, example, transition diagram.

    Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For mor

  35. Mod-01 Lec-35 Execution trace, another example (unary to binary conversion).

    Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For mor

  36. Mod-01 Lec-36 Example continued. Finiteness of TM description

    Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For mor

  37. Mod-01 Lec-37 Notion of non-acceptance or rejection of a string by a TM. Multitrack TM

    Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For mor

  38. Mod-01 Lec-38 Simulation of multitape TMs by basic model. Nondeterministic TM (NDTM).

    Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For mor

  39. Mod-01 Lec-39 Counter machines and their equivalence to basic TM model.

    Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For mor

  40. Mod-01 Lec-40 TMs can simulate computers, diagonalization proof.

    Theory of Computation by Prof. Somenath Biswas,Computer Science and Engineering, IIT Kanpur.For mor

Show More
Reviews

Ask your own question. Don't worry, it's completely free!