Theory of Computation

By Prof. Ragunath Tewari   |   IIT Kanpur
Learners enrolled: 7769
This is an introductory course on Theory of Computation intended for undergraduate students in computer science. In this course we will introduce various models of computation and study their power and limitations. We will also explore the properties of the corresponding language classes defined by these models and the relations between them. We will assume the student is comfortable in analytical reasoning and has preferably done a course on Data Structures and Algorithms.

INTENDED AUDIENCE: Computer Science undergraduate students.

PRE-REQUISITES: It is recommended that the candidate has done a course in Data Structures and Algorithms.

INDUSTRY SUPPORT: Content will be updated soon

Course Status : Completed
Course Type : Elective
Duration : 8 weeks
Start Date : 29 Jul 2019
End Date : 20 Sep 2019
Exam Date : 29 Sep 2019 IST
Category :
  • Computer Science and Engineering
Credit Points : 2
Level : Undergraduate

Page Visits

Course layout

Week 1: Finite Automata – deterministic and nondeterministic, regular operations
Week 2: Regular Expression, Equivalence of DFA, NFA and REs, closure properties
Week 3: Non regular languages and pumping lemma, DFA Minimization, 
Week 4: CFGs, Chomsky Normal Form
Week 5: Non CFLs and pumping lemma for CFLs, PDAs,  Equivalence of PDA and CFG
Week 6: Properties of CFLs, DCFLs, Turing Machines and its variants
Week 7: Configuration graph, closure properties of decidable languages, decidability properties of regular languages and CFLs
Week 8: Undecidability, reductions, Rice's Theorem, introduction to complexity theory

Books and references

Introduction to the Theory of Computation by Michael Sipser

Instructor bio

Dr.Ragunath Tewari
 is an Assistant Professor in the department of Computer Science and Engineering at the Indian Institute of Technology, Kanpur. His primary research interest is in the area of computational complexity theory. Dr. Tewari did his B.Sc. from Chennai Mathematical Institute in 2005 and Ph.D. from University of Nebraska-Lincoln in 2011.

Course certificate

  • The course is free to enroll and learn from. But if you want a certificate, you have to register and write the proctored exam conducted by us in person at any of the designated exam centres.
  • The exam is optional for a fee of Rs 1000/- (Rupees one thousand only).
  • Date and Time of Exams: 29 September 2019Morning session 9am to 12 noon; Afternoon Session 2pm to 5pm.
  • Registration url: Announcements will be made when the registration form is open for registrations.
  • The online registration form has to be filled and the certification exam fee needs to be paid. More details will be made available when the exam registration form is published. If there are any changes, it will be mentioned then.
  • Please check the form for more details on the cities where the exams will be held, the conditions you agree to when you fill the form etc.

  • Average assignment score = 25% of average of best 6 assignments out of the total 8 assignments given in the course. 
  • Exam score = 75% of the proctored certification exam score out of 100
  • Final score = Average assignment score + Exam score

  • If one of the 2 criteria is not met, you will not get the certificate even if the Final score >= 40/100.
  • Certificate will have your name, photograph and the score in the final exam with the breakup.It will have the logos of NPTEL and IIT Kanpur. It will be e-verifiable at nptel.ac.in/noc.
  • Only the e-certificate will be made available. Hard copies are being discontinued from July 2019 semester and will not be dispatched

MHRD logo Swayam logo


Goto google play store