Automata Theory (CS302.1) - Monsoon Semester 2021

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, Context-Free Grammars, Ambiguity, Chomsky Normal Form, Pushdown Automata, 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 lectures and the tutorial sessions will be held online via MS Teams. 

Schedule: 

• Lectures - Monday, Thursday (9:00 AM - 10:30 AM) 

• Tutorials - Thursday (3:30 PM - 5 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:

• Aditya Morolia (aditya.morolia(at) research.iiit.ac.in)

• Aakash Aanegola (aakash.aanegola(at)students.iiit.ac.in)

• Ashwin Mittal (ashwin.mittal(at)students.iiit.ac.in)

• Zeeshan Ahmed (zeeshan.ahmed(at)research.iiit.ac.in)

• Aakash Jain (aakash.jain(at)students.iiit.ac.in)

• Shaurya Dewan (shaurya.dewan(at)students.iiit.ac.in)

• Alapan Chaudhuri (alapan.chaudhuri(at)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.

Assignments:

• 11th Nov'21: Theory Assignment 2 has been released. Deadline for submission: 11:55 pm on Nov 21, 2021.

• 21st Oct'21: Programming Assignment has been released. Deadline for submission: 11:55 pm on Oct 31, 2021 for Problems 1 & 2 and 11:55 pm on Nov 26, 2021 for Problem 3.

• 13th Oct'21: Theory Assignment 1 has been released.  Deadline for submission: 11:55 pm on Oct 25, 2021. 

Quiz

• The Quiz will be held on Oct 28, 2021 from 9 AM - 9:45 AM. Please follow the instructions provided to you by the respective TAs.

Final Exam

The Final Exam will be held on Dec 04, 2021 from 8:30 AM - 10:00 AM. Please follow the instructions provided to you by the respective TAs. 

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.