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 H205.

Schedule: 

• Lectures - Mondays & Thursdays (3:30 AM - 5:00 PM) 

• Tutorials - Wednesdays (8:30 AM - 9:55 AM)

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:

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:

TBA

Quiz

TBA

Final Exam

TBA

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.