Automata Theory (CS302.1) - Monsoon Semester 2025
This is a core undergraduate course on Automata Theory for computer science students. The topics covered in this course include Finite State Machines, Deterministic and Non-Deterministic Finite Automata, Regular Languages, Pumping Lemma for Regular Languages, Context-Free Grammars, Ambiguity, Chomsky Normal Form, Pushdown Automata, Pumping Lemma for Regular Languages, Turing Machines, Recursive and Recursively Enumerable languages, Halting Problem and Undecidability.
The pre-requisites for the course are minimal - some familiarity with data structures and formal logic would suffice.
Course Format:
The course commences on 31st July 2025. The lectures and tutorials will be held in person in Room H105.
Schedule:
Lectures - Mondays & Thursdays (11:40 AM - 1:05 PM)
Tutorials - Wednesdays (11:40 AM - 12:40 PM)
Evaluation:
There will be two theory assignments (20% weightage) and one programming assignment (25% weightage). There will be two proctored exams: one quiz (20% weightage) and one final exam (35% weightage).
Teaching Associates:
Shreyas S (sreyas.saminathan@research.iiit.ac.in)
S Rajendraprasad (rajendraprasad.s@research.iiit.ac.in)
Kandi Jayanth Reddy (kandi.reddy@students.iiit.ac.in)
Aryaman Kolhe (aryaman.kolhe@research.iiit.ac.in)
(TBA)
Lecture slides:
Lecture 1 | Lecture 2 | Lecture 3 | Lecture 4 | Lecture 5 | Lecture 6 | Lecture 7 | Lecture 8 | Lecture 9 | Lecture 10 | Lecture 11 | Lecture 12 | Lecture 13
Assignments:
Theory Assignment 1 has been uploaded. The deadline for submission is 29th August 2025.
The Programming Assignment has been uploaded. The deadline for submission is 12th September 2025.
Theory Assignment 2 has been uploaded. The deadline for submission is 15th September 2025.
Quiz
The Quiz will be held in class (H105) from 11:40 AM - 1:00 PM on 1st September 2025.
Final Exam
The final exam will be held on 24th September 2025 from 8:30 AM - 10:00 AM.
References
M. Sipser, Introduction to the Theory of Computation, Cengage Learning 2012.
J. Hopcroft, R. Motwani and J. Ullman, Introduction to Automata Theory, Languages and Computation, Pearson Education, 2008.