Theory of Computation

A university-style theory course

This NPTEL video course has 39 lectures taught by Prof. Raghunath Tewari of IIT Kanpur. The lecture list begins with finite automata, notation, DFAs and their computation, then introduces nondeterminism and NFAs.

The order of ideas

It moves to the equivalence of NFAs and DFAs, closure properties, regular expressions, conversions between automata and expressions, non-regular languages and the pumping lemma, and DFA minimization. The visible list reaches CFGs.

• Draw the automaton for each example before the lecture solves it.
• Practise converting between NFAs, DFAs and regular expressions.
• Prove one language is non-regular using the pumping lemma on your own.