Formale Sprachen und Automaten

Die Formalen Sprachen und Automaten bilden den klassischen Kernbereich der Theoretischen Informatik. Sie sind die Grundlage für die Entwicklung der Programmiersprachen und deren Analyse und Übersetzung. Die Wurzeln dieser Theorie reichen in die Kombinatorik (A. Thue, E. Post), die Logik (A. Turing), die Linguistik (N. Chomsky) und die Biologie (A. Lindenmayer). Dabei treten zwei konträre Aspekte auf: zum einen werden Mechanismen zur Generierung von Sprachen betrachtet, z.B. Grammatiken, die festlegen, wie die Wörter der jeweiligen Sprache erzeugt werden, und zum anderen interessiert man sich für Algorithmen, die erkennen, ob ein gegebenes Wort zu der betrachteten Sprache gehört. Solche Algorithmen werden üblicherweise als spezielle Maschinenmodelle realisiert.

Als Ausgangspunkt für unsere Betrachtungen wird die auf N. Chomsky zurückgehende Hierarchie dienen, die aus den regulären, den kontext-freien, den kontext-sensitiven und den rekursiv-aufzählbaren Sprachen besteht. Dabei interessieren uns die Abschlusseigenschaften und Charakterisierungen dieser Sprachklassen durch geeignete Maschinenmodelle. Danach wollen wir uns der Zwischenklasse der wachsend kontext-sensitiven Sprachen und der Familie der McNaughton Sprachen zuwenden, wobei Sprachklassen anhand gewisser Reduktionssysteme definiert werden. Von besonderem Interesse dabei ist natürlich der Bezug zu den Klassen der Chomsky Hierarchie und wieder die Frage nach geeigneten Maschinenmodellen.

Ein weiteren Schwerpunkt werden die Sprachklassen sein, die von Grammatiken erzeugt werden, bei denen der Ersetzungsprozess durch Nebenbedingungen gesteuert wird. Schließlich sollen auch noch die sogenannten L-Systeme angesprochen werden, die ein inhärent paralleles Konzept für die Spracherzeugung darstellen, und die als ein Modell für die formale Beschreibung der Entwicklung biologischer Organismen entstanden sind.

Vorkenntnisse:

Grundvorlesungen der Informatik

Literatur:

J.~Berstel:
Transductions and Context-free Languages
Teubner Studienbücher. Teubner-Verlag, 1979
J. Dassow and G. Paun:
Regulated Rewriting in Formal Language Theory
Monographs in Theoretical Computer Science, Volume 18, Springer, Berlin, 1989.
M. Harrison:
Introduction to Formal Language Theory
Addison-Wesley, Reading, M.A., 1979
J.E. Hopcroft and J.D. Ullman:
Introduction to Automata Theory, {L}anguages, and Computation
Addison-Wesley, Reading, M.A., 1979.
G. Rozenberg and A. Salomaa:
The Mathematical Theory of L Systems
Academic Press, New York, 1980.
und Originalarbeiten