COL352 – Introduction to Automata & Theory of Computation

This fundamental material covered in this course is fairly abstract and theoretical, and will therefore require some mathematical acumen — students should, at the very least, be able to write and understand rigorous formal proofs, especially those involving various kinds of induction. Various discrete maths concepts like closures, cardinality etc. will also feature strongly, so students should be familiar with these as well. The COL202 (Discrete Mathematical Structures) course is a strict prerequisite.

• Big quizzes: 60%. We will have five big quizzes from 1845--1945, on the following tentative dates:

  1. Quiz 1: January 22, 2026

  2. Quiz 2: February 10, 2026

  3. Quiz 3: March 18, 2026

  4. Quiz 4: April 7, 2026

  5. Quiz 5: April 21, 2026

  The rooms for the quizzes will be announced closer to the dates of the quizzes. The syllabus for every quiz includes the material covered from the start of the course to the class just preceding that quiz (but not the same day).

  No re-quiz will be conducted if you miss a quiz. However, quiz 5 is intended to be an improvement quiz: each quiz has 15% weightage, so quizzes 1 through 4 make up 60%. If you feel that you have done badly in quizzes 1 through 4, you can opt to take quiz 5 and have the best three quizzes out of 1–4 be counted along with the marks of quiz 5. The decision to take quiz 5 or not must be communicated in the week prior to quiz 5.

• Major: 40%. The syllabus for the major exam will include everything covered in the course. In case you miss the major exam for medical reasons, or get an E grade overall, in order to write the remajor, you must have maintained at least 75% attendance in the course.

• Bonus: Participating in Q&A in the TA-run tutorials: 0– 5%. This incentivizes an intent to learn — for questions to receive a bonus, students must have tried the problem by themselves beforehand and be willing to engage in a discussion with the teaching staff. This bonus will only be added to the final total, and is computed as (100-(your total))/100 * (instances of participation)/5 * constant, with a choice of constant such that this value normalizes to a maximum of 5%.

Audit pass needs at least a B- overall, including at least 45% out of the 60% earmarked for quizzes.

Deviation of any sort from the IIT Delhi honour code (copying, plagiarism etc. – see here and here for more examples) will lead to a loss of grade, and potentially further disciplinary action.

We will follow notes presented in class, for the most part, which will be uploaded here. Some external references for much of the course are listed below (caveat emptor: notation/proofs used in these books might differ significantly from that used in class).

• Introduction to the theory of computation, by Michael Sipser

• Automata and computability, by Dexter C. Kozen

• Theory of computation, by Dexter C. Kozen