Automata Theory (CS302.1) - Monsoon Semester 2023


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 2023. The lectures and tutorials will be held in person in Room H205.


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:


Zeeshan Ahmed (zeeshan.ahmed@research.iiit.ac.in)

Rudransh Pratap Singh (rudransh.s@research.iiit.ac.in)

Aryaman Kolhe (aryaman.kolhe@research.iiit.ac.in)

Ronak Dhingra (ronak.dhingra@students.iiit.ac.in)

Mohammad Zaid (mohammad.zaid@students.iiit.ac.in)

S Sreyas (sreyas.saminathan@research.iiit.ac.in)

Harshit Aggarwal (harshit.aggarwal@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 | Lecture 13.


Assignments:

Theory Assignment 1 has been uploaded. Deadline for submission: 24th August 2023.

Programming Assignment has been uploaded. Deadline for submission: 4th September 2023.

Theory Assignment 2 has been uploaded. Deadline for submission: 16th September 2023.


Quiz

Quiz will be held on 28th August in H205 from 8:30 AM - 9:15 AM.


Final Exam

The Final Exam will be held on 23rd September from 4:30 PM - 6:00 PM


References