Capita Selecta Formele Talen
Second Course in Formal Language Theory
Second Course in Formal Languages and Automata Theory,
by Jeffrey Shallit, Cambridge University Press, 2008,
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.
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,
For the moment we skip the review of more
complicated models, but we will return when
I have decided to skip Chapter 2
(2) 14 Sep: III. Finite automata
(3.2 quotients, 3.3 morphisms,
3.4 advanced closure)
(3) 21 Sep: III (continued)
3.6 two-way finite automata)
28 Sep: NO MEETING
(4) 5 Okt: III (continued)
(3.8 automata and matrices,
(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)
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)
V (for the moment ignored, see Bachelor course Compiler Construction)
Ch.7 Other language classes
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,
Topics on Parsing and Formal Languages
(Robert Brijder & Frank Takes)
oct 2009 —