Inhalte

In dieser Vorlesung erschließen wir, wie solche Sprachen beschrieben werden können, und wie man Worte (Texte, Programme, Dokummente) wieder parsen kann, also wie man aus einer Folge von Buchstaben die syntaktische Struktur des entsprechenden Textes ableiten kann.

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 (aktuelle Version, Stand 2015-11-16)
• Folienskript (aktuelle Version, Handout)
• Aufgabensammlung
• Altes Folienskript (Version 2014, vollständig, aber einiges ändert sich!)
• DFA-Simulator in Python
  • FA-Simulator
  • Eingabefile EA1 akzeptiert 0^*1^*.
  • Eingabefile EA2 akzeptiert (0+1+2)^*2.
  • Eingabefile EA3 akzeptiert Worte, bei denen die Anzahl von 0 und 1 beide gerade sind.
  • Beispielausgabe
• Umwandlung von REs in (D|N)FAs
• Das flex-File aus der Vorlesung (Aufsummieren von Zahlen)
  • Eingabefile dazu (Beispiel)
• Daten für die Programmierausgabe "Flexercise/Security Audit":
  • Eingabefile 1
  • Erwartete Ausgabe zu Eingabefile 1 (Beispiel, korrigiert 2015-20-28)
  • Eingabefile 2
  • Ausgabe 2
  • Lösung: Flex-Eingabefile
  • Lösung: Makefile (optional, aber bequem)
• Übungsklausur und Lösungen (Update!)
• Übungsklausur 2014 mit Bonusaufgaben und unvollständige Lösungen dazu (jetzt auch Lösungen zu A1, z.T. A4,A5)