Automaten und formale Sprachen (SS 2020)

Vergangene Veranstaltung

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

Vorlesungsablauf

Die Vorlesung wird dieses Sommersemester aufgrund der Covid-19-Situation zunächst nicht als Präsenzveranstaltung stattfinden, sondern online. Bitte melden Sie sich im Moodle-Kurs (Link) an (es ist kein Zugangsschlüssel notwendig) für alle Materialien und weitere Informationen (werden regelmäßig aktualisiert). Die ersten Materialien werden voraussichtlich bereits in der Woche ab dem 6.4. bereitgestellt, es wird aber niemandem, der erst am 20.4. einsteigt, ein Nachteil entstehen.

Wir werden wöchentlich Videos von der Vorlesung bereitstellen. Übungsaufgaben werden wie gewohnt online abgegeben und bewertet. Auch die Besprechung der Übungen erfolgt online durch Videos. Eure Fragen zum Stoff können im Moodle-Forum oder per Mail gestellt werden und werden von uns beantwortet.

Dozentin
Prof. Dr. Barbara König

Übungsleiterin
Lara Stoltenow

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 2019 orientieren, wobei die Folien des aktuellen Semesters durchaus abweichen können. Die Arbeitsunterlagen zur Veranstaltung aus dem SS 2019 finden Sie hier.

Termine

Vorlesung

online, Links werden im Moodle bereitgestellt

vorläufig keine Präsenztermine wegen Covid-19

Tutorium

vorläufig keine Präsenztermine, bitte Moodle-Forum oder Mails an die Übungsleitung benutzen

Übungsgruppen

vorläufig keine aufgrund der Covid-19-Situation

Abgaben wie gewohnt über Moodle

Besprechung und Diskussion ebenfalls über Moodle

Übungsablauf und Bonuspunkte

Prüfungen

Mittwoch, 16.9., 13:45, Trabrennbahn Dinslaken

Sitzplan und weitere Informationen werden (später) im Moodle 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 Bearbeitung der Übungszettel und die Beteiligung an den Diskussionen im Forum 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 per Moodle möglich. Hinweise zur PDF-Abgabe siehe dort.

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.

Hinweise zu den Prüfungen

  • Am Ende des Sommersemesters wird eine schriftliche Prüfung stattfinden.
  • Ausschließlich für Studierende des Bachelor-Studiengangs "Angewandte Informatik" und nur für jene, die vor dem Wintersemester 2018/19 das Studium aufgenommen haben: Es kann eine mündliche Prüfung des Moduls "Theoretische Informatik" (in Kombination mit "Berechenbarkeit und Komplexität") abgelegt werden. Der Zeitraum wird noch bekanntgegeben.
  • Für Schülerstudenten gelten die Regelungen des Studiengangs, für den sie eingetragen sind. Es ist keine Anmeldung beim Prüfungsamt erforderlich.