Shibashis Guha (firstname@tifr.res.in)

Monday, Wednesday: 9:00 - 11

- Online over Zoom
Please send a mail to the instructor for attending lectures/seminars or to get course updates.

Regular languages: Deterministic Finite Automata (DFA) and Nondeterministic Finite Automata (NFA), Equivalence of DFA and NFA, closure properties of regular languages, regular expressions, Pumping lemma for regular languages, Myhill Nerode theorem, collapsing nondeterministic automata through bisimulation, monadic second order (MSO) logic and its relation to regular languages.

Context-free Languages: Context-free grammar (CFG), Pushdown automata (PDA), Equivalence between CFG and PDA, Closure properties of context-free languages, Pumping Lemma for CFL, Deterministic pushdown automata.

Computability: Turing machines, modifications of Turing machines, two-stack and counter machines, recursive and recursively enumerable sets, undecidability, halting problem, reduction, Rice's theorem.

Introduction to Automata Theory, Languages and Computation (1st edition) by John E. Hopcroft and Jeffrey D. Ullman, Addison-Wesley, 1979.

Automata and Computability by Dexter C Kozen, Springer, 1997.

Lecture notes posted on Acadly after every class.

Alternating finite automata

Prime languages

Unambiguous automata

Learning DFA: Angluin's algorithm

Tree automata on finite words

Transition monoid and syntactic monoid, FO definability

Parikh's theorem

Visibly pushdown automata

Decidable theories of arithmetic (weak WS1S, Presburger arithmetic)

Valid computations and decision problems for CFL

Well structured transition systems

Gödel's incompleteness theorem

Krohn-Rhodes theorem

This is a graduate course on theory of computation. The course will cover the foundations of automata theory and computability theory. In addition, there will be seminars by students on more advanced topics from textbooks and research papers in the field. There may also be a few invited lectures towards the end of the course.

Class # | Date | Topics Covered | Resources |

1 | Mo, 23/08 | introduction to the course | Lecture handouts |

2 | Sa, 28/08 | DFA, regular languages, closure properties, product construction, proof of correctness of example DFA | Section 2.2, Kozen: Lecture 4 |

3 | Mo, 30/08 | NFA, subset construction and its proof of correctness | Section 2.3 |

4 | We, 01/09 | lower bound of subset construction, epsilon-NFA | Lecture notes , HUM: Sections 2.3.6, 2.5 |

5 | Mo, 06/09 | regular expressions | Section 2.5 |

6 | We, 08/09 | equivalence of regular expressions and regular languages, Moore and Mealy machines | Sections 2.5, 2.7 |

7 | Mo, 13/09 | extended regular, star-free expressions, closure under homomorphism, right quotient, reversal | Lecture notes , textbook: Section 3.2 |

8 | We, 15/09 | pumping lemma, ultimate periodicity, Myhill Nerode relation | Lecture notes , Kozen: Lecture 12, textbook: Section 3.4 |

9 | Mo, 20/09 | Myhill Nerode theorem | Lecture notes, Section 3.4 |

10 | We, 22/09 | DFA minimization, bisimulation | Lecture notes, Kozen: Supplementary lecture B |

11 | Mo, 27/09 | bisimulation as a fixed point, bisimulation game, NFA minimization | Lecture notes, Kozen: Supplementary lecture B |

12 | We, 29/09 | monadic second order logic on words | Notes by Madhavan Mukund |

13 | Mo, 04/10 | Student seminar on Angluin's algorithm for learning DFA | Notes prepared by speaker |

14 | We, 06/10 | Büchi-Elgot-Trakhtenbrot theorem | Notes by Madhavan Mukund |

15 | We, 13/10 | Turing machines, recursive and recursively enumerable languages | Lecture notes, textbook: Sections 7.1, 7.2, 7.3, 7.5 |

16 | Sa, 16/10 | Nondeterministic Turing machines, Turing machine as a language generator | Lecture notes, textbook: Sections 7.5, 7.7 |

17 | Mo, 18/10 | multistack machines, two-counter machines, closure properties of recursive and r.e. languages | textbook: Sections 7.8, 8.2 |

18 | We, 20/10 | Diagonalization, halting problem, undecidability | Lecture notes, textbook: Section 8.3 Kozen: Lecture 32 |

19 | Mo, 25/10 | reduction, Rice's theorem | Lecture notes, textbook: Section 8.4 |

20 | We, 27/10 | Context-free grammar, pushdown automata | textbook: Sections 4.1, 4.2, 4.3, 5.2 |

21 | Mo, 01/11 | Simplification of CFG, Chomsky normal form | Lecture notes, textbook: Sections 4.4, 4.5 |

22 | We, 03/11 | Greibach normal form, equivalence between CFG and PDA | textbook: Sections 4.6, 5.3 |

23 | We, 17/11 | Pumping lemma for CFL, closure properties of CFL | textbook: Sections 6.1, 6.2 |

24 | Mo, 22/11 | membership in CFL, CYK algorithm, complementation of DPDA | textbook: Sections 6.3, 10.1, 10.2 |

25 | Sa, 27/11 | closure properties of DCFL, Parikh's theorem | textbook: Sections 10.4, Kozen supplementary lecture H |