Theory Of Computation




Courses with significant overlap with this course:

Semester of last offering:

Date of approval: dd-mmm-yyyy


Course Contents

Regular languages, Deterministic and nondeterministic nite automata, Closure properties, Languages that are and are not regular, State minimization in deterministic nite automata. Context free languages, Closure properties, Parse trees, Languages that are and are not context free, Pushdown automata. Turing machines, Turing computability, Church Turing thesis, Halting problem, Some un decidable problems. Computational complexity, Classes P and NP, NP completeness, Examples of NP complete problems. 



Number of sections:

Tutors for each section:

Schedule for Lectures:

Schedule for Tutorial:

Schedule for Labs:



Birds at IIT Kanpur
Information for School Children
IITK Radio
Counseling Service