Formale Systeme, Automaten, Prozesse (SS2017)

Am Donnerstag den 25.05. finden keine Tutorien aufgrund von Christi Himmelfahrt statt.

In dieser Woche wird es keine Minitests geben, die Globalübung wird als Sammeltermin für die Donnerstagstutorien angeboten. Die Hausaufgaben können ebenfalls dort abgegeben werden. Die Tutorien am Mittwoch finden regulär statt.

Studierende die sich nachträglich zur Klausur anmelden möchten, können das nur direkt über den Prüfungsausschuss. Diese werden dann über den Fall in der nächsten Sitzung entscheiden. Einen Antrag kann man über ein Onlineformular stellen.

Bei weiteren Fragen, , gibt es auch ein FAQ von der Fachgruppe Informatik.

Studierende, die nicht Informatik studieren, müssen sich leider selber darum kümmern bei wem sie diesen Antrag stellen müssen.

Ü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