Formale Systeme, Automaten, Prozesse (SS2023)

Alle wichtigen organisatorischen Informationen werden im ersten Vorlesungstermin vorgestellt.
Bitte meldet euch in RWTHonline für die Vorlesung/Globalübung an, damit ihr Zugriff auf den Moodle-Raum bekommt.
Wir laden die Vorlesungsmaterialien und wichtige Ankündigungen nur im Moodle-Raum hoch!

Erste Termine

  • Vorlesung: Di, 4.4
  • Tutorien: ab 13.4
  • Globalübung: Mi, 19.4
Tutorien werden in der ersten Vorlesungswoche verteilt.

Inhalt

  • Formale Systeme:
    • Terme, Wörter, Sprachen anhand von Kernbeispielen: u.a. Zahlterme, arithmetische und boolesche Terme, while-Programme.
    • Definition von Termmengen und Programmiersprachen durch Regelsysteme (Termersetzungssysteme, Grammatiken), Ableitungsbegriff, Methode der strukturellen Induktion.
    • Klassifikation von Grammatiken (Chomsky-Hierarchie) und elementare Sachverhalte zu kontextfreien Grammatiken: Normalformen, Wortproblem (Ableitbarkeitstest), Nichtleerheitstest.
  • Automaten:
    • Endliche Automaten (deterministisch, nichtdeterministisch), Abschlusseigenschaften (u.a. Produktautomaten), reguläre Ausdrücke, Nichtleerheits- und Äquivalenztest, Nachweis nichtregulärer Sprachen.
    • Kellerautomaten (deterministisch und nichtdeterministisch), Übersetzung von kontextfreien Grammatiken in Kellerautomaten als Beispiel der Implementierung von Rekursion durch Kellerspeicher.
  • Prozesse:
    • Elementare Modellierungsformen verteilter und nebenläufiger Systeme: Synchronisierte Produkte, Petrinetze und kommunizierende sequentielle Prozesse (CSP).
    • Vorstellung und Einübung anhand von Beispielen, Vergleich mit dem Grundmodell des endlichen Automaten.