Capita Selecta Formele Talen
Second Course in Formal Language Theory
(fall 2009)
Second Course in Formal Languages and Automata Theory,
by Jeffrey Shallit, Cambridge University Press, 2008,
ISBN13: 9780521865722.
You may visit
amazon.com
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.
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 contextfree)
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 twoway finite automata)
28 Sep: NO MEETING
(4) 5 Okt: III (continued)
(3.8 automata and matrices,
3.9 MyhillNerode)
(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 contextfree 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 contextfree 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 Contextsensitive 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 Contextfree
IV
Ch.5
V (for the moment ignored, see Bachelor course Compiler Construction)
Ch.7 Other language classes
VII
all slides (updated)
Notes:
Undecidable Problems for Contextfree Grammars (updated dec'16)
Abstract. We discuss some basic undecidable problems for contextfree 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 —
http://www.liacs.nl/home/hoogeboo/second
