Formale Sprachen

Prof. Dr. Henning Fernau

Vorlesungsankündigung

Diese Ausprägung der "Formalen Sprachen" wird sich deutlich von der bislang gelesenen unterscheiden.

Daher wird es (zunächst) auch keine Folien geben, sondern ich werde das Medium Tafel benutzen.

Inhaltlich werden wir uns zunächst mit Baumstrukturen beschäftigen, um dann verschiedene Mechanismen zur Beschreibung von mild kontextsensitiven Sprachen kennenzulernen.

Als Grundlage für Baumsprachen empfehle ich das TATA-Buch, wobei die Beiträge von Gecseg und Steinby im "Handbook of Formal Languages" bzw. in ihrem eigenen Buch zum Thema ergänzend hinzugezogen werden.


Gliederung:

§1 Grundlegende Definitionen zu Bäumen

§2 Nichtdeterministische endliche Baumautomaten

§3 Deterministische endliche Baumautomaten

§4 Abschlusseigenschaften

§5 Reguläre Baumgrammatiken

§6 Reguläre Baumausdrücke

 

Übungstermin

Die Übungen finden freitags von 08 - 10 h im Raum H 6 statt.