Regular and Context-Free Languages
Lecture in Winter Term 2014/2015
Content
This course is addressed to MSc students. It offers a deeper understanding of the two essential language classes that are fundamental to many areas of computer science. These are 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 of various views regarding "complexity".
The course will be given in German if all participants prefer it.
Contents:
Part I: Regular Languages
- Star-height and the star-height poblem
- Star-free languages, first-order logic and Schützenberger's Theorem
- Regular languages and circuit complexity
Part II: Context-Free Languages
- Chomsky-Schützenberger Theorem
- Generators of context-free, linear, and one counter-languages
- 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.
Organization
The course will be held in English.
Lecturer