Formale Systeme, Automaten, Prozesse

» Diese Veranstaltung wird auf deutsch gehalten.

» Es gibt einen L2P-Lernraum zu dieser Veranstaltung.

Vorlesung im Sommersemester 2008

ArtTermine/OrtBeginnVeranstalter
V3 Di 08:15-09:45 Uhr, Gr
Do 10:00-11:30 Uhr, Ro		 08.04.2008 Thomas
Ü2 Fr 11:45-13:15 Uhr, Fo 1 18.04.2008 Thomas, Spelten, Fuhs

Organisatorisches

Die Kernzeiten der dreistündigen Vorlesung sind:
  • Di 08:15-09:45 Gr
  • Do 10:00-10:45 Ro
Aufgrund vieler Konferenzen und Workshops im Semester wird es allerdings in einigen Wochen Verschiebungen geben. Diese sind die folgenden:
  • KW 15:
    • Di 08. April: keine Änderung
    • Do 10. April: 10:00-11:30 Ro
  • KW 16:
    • Di 15. April: keine Änderung
    • Do 17. April: 10:00-11:30 Ro
  • KW 17:
    • Di 22. April: fällt aus
    • Do 24. April: 10:00-10:45 Ro (Vertretung durch Alex Spelten)
  • KW 25:
    • Di 17. Juni: keine Änderung
    • Do 19. Juni: 10:00-11:30 Ro
  • KW 26:
    • Di 24. Juni: keine Änderung
    • Do 26. Juni: fällt aus
  • KW 27:
    • Di 01. Juli: keine Änderung
    • Do 03. Juli: 10:00-10:45 Ro (Vertretung durch Alex Spelten)
Die Veranstaltung ist anmeldepflichtig. Die Anmeldung erfolgt vom 24.03.-10.04.08 über das Campus-System zu den Übungsgruppen (Mittwochs und Donnerstags); für Lehramtsstudierende und Studierende der Technik-Kommunikation werden speziell die Übungsgruppen Mi 11.45 (E1) und Mi 13.45 (SG 203) empfohlen.

Für Studierende der Mathematik, die die Veranstaltung "Numerische Analysis 2" besuchen, findet der Vorführtermin Donnerstags 14:00–15:30 Uhr im Raum 4116 (Seminarraum i7) statt.

Lernziele

Beherrschung elementarer Darstellungs- und Modellierungstechniken der Informatik, angebunden an konkrete Beispiele.

  • Syntaxdefinitionen durch Regelsysteme und ihre Anwendung
  • Automaten als Grundstruktur zustandsbasierter Systeme
  • Einfache Modelle der Nebenläufigkeit (synchronisierte Produkte, Petrinetze)
  • Kenntnis der fundamentalen Algorithmen dazu (Transformation und Analyseverfahren für Automaten und Regelsysteme)

Lerninhalte

I. 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.

II. 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.

III. 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.

Vorwissen

Elementare mathematische Begriffe (aus dem 1. Semester)

Credit Points

6 ECTS