Formale Sprachen: Ausgewählte Kapitel

Die Formalen Sprachen und Automaten gehören zum 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 den Church-Rosser Sprachen zuwenden, wobei diese 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.

Weitere Themenbereiche, die angesprochen werden sollen, umfassen die folgenden

Die verwendete Literatur wird in der Vorlesung bekannt gegeben.

Voraussetzungen

Grundvorlesungen der Informatik