Automata Theory (CS302.1) - Monsoon Semester 2024


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 2024. 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: 


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)

Mayank Goel (mayank.goe@research.iiit.ac.in)

Gargi Shroff (gargi.shroff@research.iiit.ac.in)

Rijul Saigal (rijul.saigal@research.iiit.ac.in)

Anish Joishy (anish.joishy@research.iiit.ac.in)

Aadi Prasad (aadi.prasad@research.iiit.ac.in)

 Devika Umesh Bej (devika.bej@research.iiit.ac.in)


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| LLecture 13


Assignments:

12th August 2024: Theory Assignment 1 (Submission deadline: 25th August) and Programming Assignment 1 (Submission Deadline: 16th September) have been released. 

29th August 2024: Theory Assignment 2 has been released. Deadline: 19th September 2024


Quiz

The Quiz will be held in class (H105) from 15:30 hrs - 16:15 hrs on 26th August 2024.


Final Exam

Final Exam is on Friday, 20th September 2024.


References