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

Type | Time/Place | Lecturer | |
---|---|---|---|

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 |

## Contents

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.