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