Theory of Computation

Class Instructor: Prof. (Dr.)  Girija Limaye

Anonymous feedback form: chick here

Lecture-wise details: click here

Resources: Lecture notes, Lecture videos

Practice problem sets:

• June 29: Set #0 (prerequisites of the course)

• Jul 9: Set #1 (DFA, NFA)

• Jul 19: Set #2 (regex, regex->NFA)

• Jul 28: Set #3 (regular languages: closure. decision, TPL, MNT)

• Aug 11: Set #4 (equivalence testing of DFAs, CFGs, CFLs, ambiguity)

• Aug 23: Set #5 (CFG, PDA, non-CFLs)

• Sept 4: Set #6 (Chomsky Hierarchy, DFA correctness, TMs and variants)

• Sept 16: Set #7 (everything after PPS 6)

Practice problem set solutions:

• PPS 1 to 3

• PPS 4 to 7

Practice Quiz solutions:

• Sept 2