| Dozent | Henning Fernau und Klaus-Jörn Lange |
| Sprechstunde | Do 13.30-14.30 und nach Vereinbarung, Raum 009, Sand 13, Tel. 29-77567 |
| Zeit | Di 16-18 und Do 16-18 |
| Umfang | 4+2h |
| Begin | in der ersten Vorlesungswoche |
| Vorbesprechung | - |
| Ort | Morgenstelle, N9 |
| Turnus | jedes Sommersemester |
| Prüfungsfach | Theoretische Informatik |
Beschreibung:
Ein Grundelement der Theorie Formaler Sprachen ist die endliche
Beschreibung potentiell unendlicher Mengen von Wörtern, sogenannten
formalen Sprachen. Diese treten als formale Beschreibung von
Problemen, Funktionen oder sonstiger Objekte auf.
Wesentlicher Inhalt der Vorlesung sind verschiedene Grammatikmodelle sowie deren Eigenschaften hinsichtlich Beschreibungsmächtigkeit und Abschlußeigenschaften.
Behandelt werden auch Beziehungen zu Automatenmodellen und damit zusammenhängend Algorithmen für die Ermittlung der Ableitbarkeit von Wörtern sowie Fragen zur Entscheidbarkeit und zur Komplexität von Problemen, die sich bei der Beschäftigung mit Grammatiken und Automaten natürlicherweise ergeben.
Voraussetzungen:
Bemerkungen:
Literaturliste: