Formale Systeme, Automaten, Prozesse (SS2017)

Am Mittwoch, dem 21.06., finden aufgrund des RWTH Sports- Day (DIES) die Tutorien nicht statt.

Wegen des Sommerfestes der Informatik am Freitag, dem 23.06., fällt in der gleichen Woche die Globalübung aus.

Während der Tutorien am Donnerstag Nachmittag, dem 22.06., findet eine Präsenzübung in "Lineare Algebra" statt; deshalb wird es in dieser Woche keine Minitests geben. Die Hausaufgaben können in der Vorlesung am Montag, dem 26.06., abgegeben oder bei Teilnahme an einem der Tutorien am Donnerstag Morgen um 8.30 Uhr dort eingereicht werden.

Ü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