Regular and Context-Free Languages: Advanced Results

» This course is given in English.

Auf Wunsch aller Hörer kann die Veranstaltung auch auf deutsch gehalten werden.

Lecture in Winter Term 2013/14

Type Time/Place Lecturer
V2 Mon 13:00–14:30, Seminar Room i7 ( R 4116 ) Thomas
Ü1 still to be fixed Thomas Gelderie

The start is on October 14, 13:00-14:00h.


This course is addressed to MSc students. It offers a deeper  understanding of the two essential language classes that are fundamental in many areas of computer science: the regular and the context-free languages. Although some of the presented results are quite old, they have not lost their significance. Also some of the oldest open problems of theoretical computer science belong to this area.

Applications will be mentioned, but the emphasis is on theory, with two main topics: alternative descriptions of languages in different frameworks, and classification of languages in terms various views of "complexity".

The course will be given in German if all participants prefer this.


Part I: Regular Languages
1. Star-height and the star-height poblem
2. Star-free languages, first-order logic and Schützenberger's Theorem
3. Regular languages and circuit complexity

Part II: Context-Free Languages
4. Chomsky-Schützenberger Theorem
5. Generators of context-free, linear, and one counter-languages
6. Deterministic context-free languages


Previous Knowledge

Knowledge in automata theory from the basic courses is mandatory. Knowledge from a further lecture on automata theory (such as 'Applied Automata Theory' or 'Infinite Computations') is helpful.