Automata Theory (CS302.1) - Monsoon Semester 2026


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 30th July 2025. The lectures and tutorials will be held in person in Room H105.


Schedule: 


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: 


TBA


Lecture slides:



Assignments:

Theory Assignment 1 has been uploaded. The deadline for submission is TBA.

The Programming Assignment has been uploaded. The deadline for submission is TBA.

Theory Assignment 2 has been uploaded. The deadline for submission is TBA.


Quiz

The Quiz will be held in class (H105) from 11:40 AM - 1:00 PM on TBA.


Final Exam

The final exam will be held on TBA.


References