Formale Systeme, Automaten, Prozesse (SS2017)

Die Noten zur zweiten Klausur sind im Übungssystem einsehbar.

Noten Notenschnitt: 3.4

Übungssystem

https://aprove.informatik.rwth-aachen.de/fosap17/login

Zulassungsvoraussetzungen für die Klausur

  • 50% der Punkte in den Hausaufgaben.
  • 50% der Punkte in den Präsenzübungen die in den Tutorien stattfinden.

Voraussetzungen

Grundkenntnisse in Mathematik.

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.

Folien

Die Folien zur Vorlesung (jetzt in toner- und tintensparender, umweltfreundlicher Form) sind hier erhältlich:

Übungen

Extras