MTL783/MTL7783: Theory of Computation
Monsoon semester, 2026-27
Lectures by:
Ashutosh Rai.
Time of the class:
Tuesdays, Wednesdays, and Fridays 9:00am to 9:50am.
Office hours:
by email appointment.
Teaching assistants:
Mohit Singh Karki : maz248169@iitd.ac.in
Siddharth : mt6222028@iitd.ac.in
Syllabus: We will roughly cover the following topics: Introduction to the Theory of Computation: Proof Techniques, Basic
concepts of language, Grammar and Automata; Chomsky Hierarchy,
Regular Languages, Finite automata, Equivalence, DFA and NFA,
Minimization, Myhill-Nerode Theorem; Context Free Grammar,
Pushdown Automata their equivalenece and Application, Properties of
Context-Free Languages; Turing Machine, Recursive and Recursively
Enumerable Languages; undecidability, Rice’s Theorem, Post’s
Correspondence Problem, Complexity Theory, Intractable Problems.
Course Material:
We will follow the book "Introduction to the Theory of Computation" by Michael Sipser [Sipser] for which a low price edition is available in India.
I might sometimes refer to some other material, in which case I will mention that. Students can also refer to these additional texts if they are interested.
- Introduction to Automata Theory, Languages, and Computation (Pearson) by Hopcraft, Motwani, and Ullman [HMU]
- Automata and Computability (Springer) by Dexter Kozen [DK]
Credits:
The course will be evaluated on a 100 point scale.
There will be 2 quizzes of 15 points each.
The minor and major will be worth 30 and 35 points respectively.
To audit pass the course, you need to have at least 40 points.
5 points will be there attendance. For at least 80 percent attendance you get 5 points, for at least 75 but less than 80, you get 2 points, and no attendance points for less than 75 percent attendance. Attendance will be done through rollcall.
Anyone found using unfair means for attendance will lose all the attendance marks, and repeated violations can face further consequence, including, but not limited to, lowering of a grade or failing the course.
There will be only one make-up exam to make up for missed quizzes or minor. One can appear in at most one make-up exam, either the re-quiz or the re-minor, both of which will be conducted before the major, and would contain the full syllabus.
Attendance of 75% is required to get credits for the course as per institute rules.
Lectures and References:
Lecture 1: Introduction to the course, prerequisites and preliminary concepts. Reference: [Sipser] Chapter 0.
Lecture 2: (Deterministic) Finite Automaton: examples, state diagrams, definition. Reference: [Sipser] 1.1.
Lecture 3: Designing finite automata, formal definition of computation, Regular Languages: closure under union. Reference: [Sipser] 1.1.
Lecture 4: Nondeterministic Finite Automaton: intuition and examples. Reference: [Sipser] 1.2.
Lecture 5: Nondeterministic Finite Automaton: definition and computation, equivalence of NFAs and DFAs, closure of regular languages under various operations. Reference: [Sipser] 1.2.
Lecture 6: Regular Expressions: oprations, definition, examples, regular expression to NFA. Reference: [Sipser] 1.3.
Lecture 7: Automata to regular expressions: GNFA. Reference: [Sipser] 1.3.
Lecture 8: Nonregular Languages: Pumping lemma and proof, examples. Reference: [Sipser] 1.4.
Lecture 9: DFA minimization: table filling algorithms, equivalent states. Reference: [DK] 13,14.
Lecture 10: Myhill-Nerode Equivalence and Myhill-Nerode Theorem. Reference: [DK] 15,16.
Lecture 11: Context-Free Grammars. Reference: [Sipser] 2.1.
Lecture 12: Context-Free Grammars: parse trees, ambiguity, Chomsky Normal Form. Reference: [Sipser] 2.1.
Lecture 13-14: Pushdown Automata: intuition and definition, formal definition of computation, designing PDAs. Reference: [Sipser] 2.2.
Lecture 15-16: Equivalence of CFGs and PDAs: Reference: [Sipser] 2.2.
Lecture 17: Quiz I.
Lecture 18: Pumping Lemma for PDAs: Reference: [Sipser] 2.3.
Lecture 19: : Closure properties of CFLs. References: [Notes], also, [HMU] .
Lecture 20: CYK Algorithm. Reference: [Notes], also, [DK] 27.
| |