Completed
Mod-01 Lec-07 A generalization of pumping lemma, nondeterministic finite automata (NFAs)
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.
