Automata Theory (CS302.1) - Monsoon Semester 2022
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 28th July 2022 and the lectures will be held offline in Room H205.
Schedule:
Lectures - Mondays & Thursdays (8:30 AM - 9:55 AM)
Tutorials - Tuesdays (2:00 PM - 3:30 PM) Venue: Room H105
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)
Alapan Chaudhuri (alapan.chaudhuri@research.iiit.ac.in)
Rutvij Menavlikar (rutvij.menavlikar@research.iiit.ac.in)
Kushagra Garg (kushagra.garg@research.iiit.ac.in)
Mihir Bani (mihir.bani@research.iiit.ac.in)
Rudransh Pratap Singh (rudransh.s@research.iiit.ac.in)
Shashwat Goel (shashwat.goel@research.iiit.ac.in)
Pramod Rao (pramod.b@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:
Assignment (Section 1 and Section 2) has been uploaded. Deadline for submission: Section 1 - 24th August (11:59 pm), Section 2 - 16th September (11:59 pm).
Quiz
To be held on 25th August 2022 from 8:30 AM - 9:15 AM (Venue: H205).
Final Exam
To be held on Monday 19th September (8:30 am - 10:00 am). Venue: H203
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.