Logic and
Theory of
Discrete Systems

Informatik 7

Regular and Context-Free Languages: Advanced Results

Lecture in Winter Term 2014/2015

This course is given in English. It may be given in German if all participants prefer this.

V2 Thu 10:15–11:45, seminar room of i7 (room 4116) Thomas Campus link
Ü1 Mo  10:15–11:00, seminar room of i7 (room 4116) Thomas, Lang Campus link


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".

Structure of the course

Part I: Regular Languages
1. Star-height and the star-height problem
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.

Learning Material

The learning material is available in the L2P course room. Please register for the course in order to get access to the course room.