Theory of Computation


Lecture 1 - What is theory of computation? Set membership problem, basic notions like alphabet, strings, formal languages


Lecture 2 - Introduction to finite automaton


Lecture 3 - Finite automata continued, deterministic finite automata(DFAs), language accepted by a DFA


Lecture 4 - Regular languages, their closure properties


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


Lecture 6 - More examples of nonregular languages, proof of pumping lemma, pumping lemma as a game, converse of pumping lemma does not hold


Lecture 7 - A generalization of pumping lemma, nondeterministic finite automata (NFAs), computation trees for NFAs


Lecture 8 - Formal description of NFA, language accepted by NFA, such languages are also regular


Lecture 9 - 'Guess and verify' paradigm for nondeterminism


Lecture 10 - NFA's with epsilon transitions


Lecture 11 - Regular expressions, they denote regular languages


Lecture 12 - Construction of a regular expression for a language given a DFA accepting it. Algebraic closure properies of regular languages


Lecture 13 - Closure properties (Continued...)


Lecture 14 - Closure under reversal, use of closure properties


Lecture 15 - Decision problems for regular languages


Lecture 16 - About minimization of states of DFAs. Myhill-Nerode theorem


Lecture 17 - Continuation of proof of Myhill-Nerode theorem


Lecture 18 - Application of Myhill-Nerode theorem. DFA minimization


Lecture 19 - DFA minimization (Continued...)


Lecture 20 - Introduction to context free languages (cfls) and context free grammars (cfgs). Derivation of strings by cfgs


Lecture 21 - Languages generated by a cfg, leftmost derivation, more examples of cfgs and cfls


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


Lecture 23 - Towards Chomsky normal forms: elimination of useless symbols, analysis of reachable symbols, generating nonterminals, order of substeps matter


Lecture 24 - Simplification of cfgs continued, Removal of epsilon productions: algorithm and its correctness


Lecture 25 - Elimination of unit productions. Converting a cfg into Chomsky normal form. Towards pumping lemma for cfls


Lecture 26 - Pumping lemma for cfls. Adversarial paradigm


Lecture 27 - Completion of pumping lemma proof. Examples of use of pumping lemma. Converse of lemma does not hold. Closure properties of cfls


Lecture 28 - Closure properties continued. cfls not closed under complementation


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


Lecture 30 - More decision problems. CYK algorithm for membership decision


Lecture 31 - Introduction to pushdown automata (pda)


Lecture 32 - pda configurations, acceptance notions for pdas. Transition diagrams for pdas


Lecture 33 - Equivalence of acceptance by empty stack and acceptance by final state


Lecture 34 - Turing machines (TM): motivation, informal definition, example, transition diagram


Lecture 35 - Execution trace, another example (unary to binary conversion)


Lecture 36 - Example continued. Finiteness of TM description, TM configuration, language acceptance, definition of recursively enumerable (r.e.) languages


Lecture 37 - Notion of non-acceptance or rejection of a string by a TM. Multitrack TM, its equivalence to standard TM. Multitape TMs


Lecture 38 - Simulation of multitape TMs by basic model. Nondeterministic TM (NDTM). Equivalence of NDTMs with deterministic TMs


Lecture 39 - Counter machines and their equivalence to basic TM model


Lecture 40 - TMs can simulate computers, diagonalization proof


Lecture 41 - Existence of non-r.e. languages, recursive languages, notion of decidability


Lecture 42 - Separation of recursive and r.e. classes, halting problem and its undecidability