Theory of Computation

Instructor: Prof. Somenath Biswas, Department of Computer Science and Engineering, IIT Kanpur.

The objective of the course is to provide an exposition first to the notion of computability, then to the notion of computational feasibility or tractability. We first convince ourselves that for our purpose it suffices to consider only language recognition problems instead of general computational problems. We then provide a thorough account of finite-state automata and regular languages, not only because these capture the simplest language class of interest and are useful in many diverse domains. We then consider context grammars and languages, and their properties. Next, we consider Turing machines (TMs). We then obtain the separation of the classes recursively enumerable, and recursive. A number of TM-related problems are shown to be undecidable. Finally, we introduce the notion of feasible or tractable computation.

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