Second Course in Formal Language Theory

(fall 2009)

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

The author has a webpage on the book, where one can find errata.

Description: studiegids@leidenuniv.nl
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)

Classes:

(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)
28 Sep: NO MEETING
(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)

Slides:
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)
Ch.7 Other language classes VII