Regular and Context-Free Languages: Advanced Results
» This course is given in English.
» There is an L2P learning room for this course.
Lecture in Winter Term 2009/2010
| Type | Time/Place | Start | Lecturer |
|---|---|---|---|
| V2 | Thu 13:15–14:45, AH II | 15 October 2009 | Thomas |
| Ü1 | Tue 13:15–14:00, AH I | 20 October 2009 | Thomas, Zimmermann |
Contents
This course is addressed to MSc students and diploma 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 is an update of the course "Strukturtheorie regulärer und kontextfreier Sprachen" previously offered to diploma students. Some algebraic topics (that belong more to mathematics) are cancelled; some others (on context-free languages that are relevant to applications) are added.
Contents:- 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
Literature
The main sources are- H. Straubing, Finite Automata, Formal Logic, and Circuit Complexity, Birkhäuser, Boston 1994.
- J. Berstel, Transductions and Context-Free Languages, Teubner, Stuttgart
- M.A. Harrison, Introduction to Formal Language Theory, Addison-Wesley, Reading, Mass. 1978.
Previous Knowledge
Knowledge of automata theory as presented in basic courses is required for participation.
Credit Points
4 ECTS