Capita Selecta Formele Talen

Second Course in Formal Language Theory

book cover

(fall 2009)

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

You may visit to have a (first) look at the book.

Shallit has a webpage on the book, where one can find errata. See also his course Formal Languages and Parsing at the University of Waterloo.

Schedule: monday Sep 7 - Nov 23, 11:15 - 13:00, Snellius.

Requirement: Basic knowledge in Automata and Formal Languages, e.g., as in the Leiden Bachelor courses Fundamentele Informatica 2 and 3. (Gehaald, alleen gevolgd is niet genoeg)


(1) 7 Sep: I. Review (1.3 regular languages, 1.4 finite automata, 1.5 context-free)
For the moment we skip the review of more complicated models, but we will return when appropriate.
I have decided to skip Chapter 2 on Combinatorics
(2) 14 Sep: III. Finite automata (3.2 quotients, 3.3 morphisms, 3.4 advanced closure)
(3) 21 Sep: III (continued) (3.5 transducers, 3.6 two-way finite automata)
(4) 5 Okt: III (continued) (3.8 automata and matrices, 3.9 Myhill-Nerode)
(5) 12 Okt: III (continued) (3.10 Minimization of finite automata, 3.12 Partial orders and regular languages)
(6) 19 Okt: IV (4.1 Closure properties, 4.2 Unary context-free languages, 4.6 Parikh's theorem)
(7) 26 Okt: IV (cont) (4.3 Ogden's lemma, 4.4 Applications of Ogden's lemma, 4.5 The interchange lemma)
(8) 2 Nov: IV (cont) (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).
(9) 9 Nov: VI. (4.8++ Automata for linear languages, 7.1 Context-sensitive languages, 7.2 The Chomsky hierarchy)

Ch.1 Review I 1 - I 9 (21 Sep 09)
Ch.3 Finite state III 1- III 23 (21 Sep 09) III 24 - III 36 (5 Oct 09)
Ch.4 Context-free IV
Ch.5 V (for the moment ignored, see Bachelor course Compiler Construction)
Ch.7 Other language classes VII

all slides (updated)

Undecidable Problems for Context-free Grammars (updated dec'16)
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.

Handy, for your homework: the online Finite State Machine Designer, with output in LaTeX/tikz.

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

oct 2009 —