NPTEL : Theory of Computation (Computer Science and Engineering)

Co-ordinators : Prof. Somenath Biswas


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