Automaten und formale Sprachen (SS 2019)

Vergangene Veranstaltung

Diese Seite bezieht sich auf eine Vorlesung aus vorherigen Jahren. Aktuelle Termine und Arbeitsmaterialien sind hier zu finden.

Dozentin
Prof. Dr. Barbara König

Übungsleitung
Lara Stoltenow
Dennis Nolte

Inhalt und Lernziele

Die Theorie der formalen Sprachen bildet die Grundlage für viele andere Gebiete der Informatik, beispielsweise für Informationsverarbeitung, Compilerbau, Verifikation oder Modellierung. Im Rahmen dieser Veranstaltung werden die Grundlagen der formalen Sprachen vermittelt und Fertigkeiten im Umgang mit Automaten und Grammatiken eingeübt. Außerdem soll vermittelt werden, in welchen Bereichen diese Theorie zur Anwendung kommt. Im Einzelnen wird dabei behandelt:

  • Grammatiken, Chomsky-Hierarchie
  • Wortproblem, Syntaxbäume
  • Reguläre Sprachen (Endliche Automaten, Reguläre Ausdrücke, Pumping-Lemma, Äquivalenzrelationen und Minimalautomaten, Abschlusseigenschaften, Entscheidbarkeit, Anwendung: Verifikation eines Protokolls zum wechselseitigen Ausschluss)
  • Kontextfreie Sprachen (Normalformen, Pumping-Lemma, CYK-Algorithmus, Kellerautomaten, deterministisch kontextfreie Sprachen, Abschlusseigenschaften, Entscheidbarkeit)
  • Kontextsensitive und Typ-0-Sprachen

Die Vorlesung wird sich inhaltlich stark an der Vorlesung aus dem SS 2018 orientieren, wobei die Folien des aktuellen Semesters durchaus abweichen können. Die Arbeitsunterlagen zur Veranstaltung aus dem SS 2018 finden Sie hier.

Termine

Vorlesung

Dienstags, 12-14 Uhr in LB 104

Die Vorlesung beginnt am Dienstag, den 9. April.

Tutorium

Montag, 12-14, LF 035
ab dem 29. April

Übungsgruppen

  • G1 (deutsch): Mo, 10-12, LF 035 (Katja Poltermann)
  • G2 (englisch): Di, 8-10, LE 120 (Katja Poltermann)
  • G3 (deutsch): Di, 16-18, LE 103 (Katja Poltermann)
  • G4 (deutsch): Mi, 10-12, LB 117 (Annika Österdiekhoff)
  • G5 (deutsch): Mi, 12-14, LC 137 (Matthias Schaffeld)
  • G6 (deutsch): Fr, 10-12, LC 137 (Patrick Neumann)

Die Übungsgruppen beginnen in der dritten Vorlesungswoche (ab dem 23. April).

Übungsablauf und Bonuspunkte

Prüfungen

Die mündlichen Prüfungen finden vom 17.-21. Februar 2020 im Raum LF 264 statt. Ab sofort liegen im Sekretariat LF 227 Terminlisten aus, in die Sie sich eintragen können.

Die schriftliche Prüfung findet am Freitag, 28. Februar 2020, um 15:30 Uhr statt. Der Raum wird noch bekanntgegeben.

Hinweise zu den Prüfungsformen

Arbeitsmaterial

Links

Literatur

  • Uwe Schöning: "Theoretische Informatik - kurz gefasst"
    Spektrum, 2008. 5. Auflage.
    ISBN: 978-3-8274-1824-1 
    Der Inhalt der Vorlesung orientiert sich besonders an Kapitel 2 und 3.
  • Hopcroft, Motwani, Ullman: "Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie"
    Pearson Studium, 2006. 2. Auflage.
    ISBN: 978-3-8273-7020-4 
  • Michael Sipser: "Introduction to the theory of computation"
    Thomson Course Technology, 2008. 2. internationale Auflage.
    ISBN: 978-0-619-21764-8

Alle drei Bücher stehen auch in der Bibliothek zur Verfügung.

Hinweise

Zielgruppe

Diese Vorlesung kann von Studierenden verschiedener Studiengänge gehört werden. Insbesondere handelt es sich dabei um:

  • Studierende im Duisburger Bachelor-Studiengang "Angewandte Informatik (Ingenieur- und Medieninformatik)"
  • Studierende mit Nebenfach Informatik
  • Studierende im Master-Studiengang "International Studies in Engineering"

Hinweise zu den Übungen

Die Teilname an den Übungen und die Bearbeitung der Übungszettel ist dringend erwünscht, da sich ein Großteil des Stoffes durch Anwendung am Beispiel deutlich besser verstehen lässt als bei reinem Studium der Folien.

Die Abgabe der Übungen ist in Papierform oder per Moodle möglich. Die Papierabgaben müssen in den mit "Automaten und Formale Sprachen" beschrifteten Briefkasten neben Raum LF 259 geworfen werden. Hinweise zur PDF-Abgabe siehe Moodle.

Den Bonus von einer Notenstufe (z.B. 2,0 statt 2,3) erhält, wer am Ende der Vorlesung mindestens 50% der Übungspunkte (also 120 Punkte oder mehr) erhalten hat. Es gibt einmalig die Möglichkeit 10 Punkte durch Vorrechnen einer Aufgabe in den Übungsgruppen zu erhalten.

Hinweise zu den Prüfungen

  • Studierende des Bachelor-Studiengangs "Angewandte Informatik", die vor dem Wintersemester 2018/19 das Studium aufgenommen haben,  können eine mündliche Prüfung des Moduls "Theoretische Informatik" (in Kombination mit "Berechenbarkeit und Komplexität") ablegen. Im Sommersemester finden die mündlichen Prüfungen vom 5.-9.8.2019 statt. Im Sekretariat LF 227 liegen ab sofort Terminlisten aus, in die Sie sich eintragen können.
  • Für alle anderen Studierenden (siehe Hinweis) wird am Ende dieses Sommersemesters eine schriftliche Prüfung stattfinden.
  • Für Schülerstudenten gelten die Regelungen des Studiengangs, für den sie eingetragen sind. Es ist keine Anmeldung beim Prüfungsamt erforderlich.