Shibashis Guha (firstname@tifr.res.in)

Tuesday, Thursday: 9 - 10:30

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

Introduction to Automata Theory, Languages and Computation (3rd edition) by John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Addison-Wesley, 2006. (HUM)

Lecture notes posted on Acadly after every class.

Alternating finite automata

Two-way finite automata

Unambiguous automata

Tree automata on finite words

Transition monoid and syntactic monoid

Parikh's theorem

Visibly pushdown automata

Decidable theories of arithmetic (weak WS1S, Presburger arithmetic)

Valid computations and decision problems for CFL

Linear bounded automata and context-sensitive languages

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 | Tu, 16/02 | Introduction to the course, DFA | Textbook: Sections 2.1, 2.2 |

2 | Th, 18/02 | regular languages, closure properties, product construction, proof of correctness of example DFA | Kozen: Lecture 4 |

3 | Tu, 23/02 | nondeterministic finite state automata, subset construction, equivalence with DFA | Textbook: Section 2.3 |

4 | Th, 25/02 | lower bound of subset construction, epsilon-NFA | HUM: Sections 2.3.6, 2.5 |

5 | Tu, 02/03 | discussion of assignments and seminars, regular expressions | Textbook: Section 2.5 |

6 | Th, 04/03 | equivalence of regular expressions and regular languages | Textbook: Section 2.5 |

7 | Tu, 09/03 | finite automata with output | Textbook: Section 2.7 |

8 | Th, 11/03 | closure under homomorphism, inverse homomorphism, right quotient, reversal | Kozen Lecture 10, Textbook: Section 3.2 |

9 | Tu, 16/03 | student seminar on two-way auotmata | Textbook: Section 2.6 |

10 | Th, 18/03 | student seminar on alternating auotmata | Paper by G. Jiraskova, Handbook of formal languages |

11 | Tu, 23/03 | pumping lemma for regular languages, Myhill Nerode relations | Textbook: Sections 3.1, 3.4, lecture notes on Acadly |

12 | Th, 25/03 | Myhill Nerode theorem, DFA minimization | Textbook: Sections 3.4, lecture notes on Acadly |

13 | Tu, 30/03 | monadic second order logic | Notes by Madhavan Mukund, lecture notes on Acadly |

14 | Th, 01/04 | equivalence of MSO logic and regular languages | Notes by Madhavan Mukund |

15 | Tu, 06/04 | student seminar on Algebraic automata theory | Notes prepared by speaker |

16 | Th, 08/04 | student seminar on basics of tree automata | Chapter 1, Tree automata techniques and applications |

17 | Tu, 13/04 | guest lecture on Transducers by Vrunda Dave (part 1) | Link to recorded video on Acadly |

18 | Th, 15/04 | guest lecture on Transducers by Vrunda Dave (part 2) | Link to recorded video on Acadly |

19 | Tu, 20/04 | Turing machines, recursive and r.e. languages | Textbook: Sections 7.2, 7.3 |

20 | Th, 22/04 | Modifications of Turing machines | Textbook: Section 7.5 |

21 | Su, 02/05 | Turing machine as generator, stack and counter machines | Textbook: Sections 7.7, 7.8 |

22 | Tu, 04/05 | properties of recursive and r.e. languages, undecidability of halting problem | Textbook: Sections 8.1, 8.2, 8.3 |

23 | Th, 06/05 | reductions, Rice's theorem | Textbook: Section 8.4 |

24 | Tu, 11/05 | bisimulation and minimization of NFA | Kozen, supplementary lecture B |

25 | Th, 13/05 | bisimulation as a fixed point, discussion of assignment solutions | Lecture notes on Acadly |

26 | Tu, 18/05 | guest lecture on beyond undecidability by Prof. Paritosh Pandya | Kozen: supplementary lecture J |

27 | Th, 20/05 | PDA, DPDA, equivalence of acceptance by empty stack and by final states | Textbook: Sections 5.1, 5.2, 5.3 |

28 | Fr, 21/05 | guest lecture on recursive functions by Prof. Paritosh Pandya | notes by Pierre Wolper,Kozen: lecture 36, lecture notes on Acadly |

29 | Tu, 25/05 | CFG, parse trees, ambiguity, simplification of CFG | Textbook: Sections 4.2, 4.3, 4.4 |

30 | Th, 27/05 | Chomsky normal form, Greibach normal form, equivalence between CFG and PDA | Textbook: Sections 4.5, 4.6, 5.3 |

31 | Tu, 01/06 | pumping lemma for CFL, closure properties of CFL | Textbook: Sections 6.1, 6.2 |

32 | Th, 03/06 | closure properties and decision problems of CFL | Textbook: Sections 6.2, 6.3 |

33 | Sa, 05/06 | student seminar on Gödel's incompleteness theorem | Kozen: Lectures 38, 39, Supplementary Lecture K |

34 | Tu, 08/06 | Rice's theorem for recursively enumerable index sets | Textbook: Section 8.4 |

35 | Th, 10/06 | student seminar on Krohn Rhodes theorem | Notes prepared by speaker |