Second Course in Formal Language Theory

(fall 2009)

Second Course in Formal Languages and Automata Theory,
by Jeffrey Shallit, Cambridge University Press, 2008,
ISBN-13: 9780521865722.

Shallit has a webpage on the book, where one can find errata. The course is now behind login, as (regretably) universities now do.

I. Review (1.3 regular languages, 1.4 finite automata, 1.5 context-free)
We skip Chapter 2 on Combinatorics
III. Finite automata (3.2 quotients, 3.3 morphisms, 3.4 advanced closure, 3.5 transducers, 3.6 two-way finite automata, 3.8 automata and matrices, 3.9 Myhill-Nerode, 3.10 Minimization of finite automata, 3.12 Partial orders and regular languages)
IV. (4.1 Closure properties, 4.2 Unary context-free languages, 4.6 Parikh's theorem, 4.3 Ogden's lemma, 4.4 Applications of Ogden's lemma, 4.5 The interchange lemma, 4.7 Deterministic context-free languages, 4.8 Linear languages)
We now move to Chap.7, because I want to learn about two very basic results there (Immerman and Szelepcsényi; Cook).
VII. (4.8++ Automata for linear languages, 7.1 Context-sensitive languages, 7.2 The Chomsky hierarchy)

Slides: all slides (updated)

Notes:
Undecidable Problems for Context-free Grammars (updated feb'17)
Abstract. We discuss some basic undecidable problems for context-free languages, starting from Valid and invalid computations of TM's: a tool for proving CFL problems undecidable, Section 8.6 of the famous "Cinderella Book" by Hopcroft and Ullman.

For 2010 we find a change of lecturer, title and selection of topics, Topics on Parsing and Formal Languages (Robert Brijder & Frank Takes)

Later years. This course used to be available as an elective "reading" course.