Formale Sprachen und Automatentheorie

Vorlesung an der DHBW Stuttgart, 2014.

Inhalte

Formale Sprachen bilden die Grundlage für die Beschreibung und Umsetzung von Eingabesprachen für Computer - von speziellen Konfigurationssprachen über HTML und XML bis hin zu echten Programmiersprachen wie C, JAVA, und LISP. Aber auch die Verarbeitung und das Verständnis von natürlichsprachlichen Texten stützt sich auf formale Sprachen.

In dieser Vorlesung erschließen wir, wie solche Sprachen beschrieben und geparst werden können.

Die Automatentheorie bietet dafür Berechnungsmodelle, mit denen wir verschiedene Klassen von Sprachen erkennen und verarbeiten können. Endliche Automaten können eine Sprache z.B. in Schlüsselworte, Bezeichner, Hilfssymbole und elementare Werte zerlegen. Mächtigere Automatenmodelle können zunehmend kompliziertere Konstrukte erkennen und verarbeiten. Die Turing-Maschine ist ein Modell eines universellen Computers. Turing-Maschinen können mit einfachsten Mitteln die selben Berechnungen durchführen wie idealisierte Versionen unserer heutigen Computer.

Unterlagen

Folienskript (alte Version)
Folienskript (neue Version, Stand 2014-11-21)
Folienskript (neue Version, Handout-Version)
miu.py
Programmieraufgabe Woche 2
- EA1 akzeptiert 0^*1^*.
- EA2 akzeptiert (0+1+2)^*2.
- EA3 akzeptiert Worte, bei denen die Anzahl von 0 und 1 beide gerade sind.
- Beispielausgabe
- FA-Simulator
Für Neugierige:
- NFA-DFA-Konverter in Python
- Eingabe-File (in GraphViz/dot-Format)
Das lex-File aus der Vorlesung
Daten für die Programmierausgabe vom 22.10.2014:
Aufgabensammlung (V2 von 2014-11-10) und Lösungsskizzen
Der Tischrechner vom 12.11.2014
- Der Bison-Code: scicalcparse.y
- Der Flex-Code: scicalclex.l
- Optional, aber bequem: Makefile

DHBW Stuttgart, Prof. Dr. Stephan Schulz