SS 2015: Automaten und formale Sprachen

Dozentin:
Prof. Dr. Barbara König (Email)

Übungsleitung:
Jan Stückrath (Email)

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

Hinweise

  • 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"
  • 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 sowohl online über MOODLE als auch in Papierform möglich. Die Papierabgaben müssen in den mit "Automaten und Formale Sprachen" beschrifteten Briefkasten neben Raum LF 259 geworfen werden.
    Es gilt folgende Bonuspunkteregelung:
    Den Bonus von einer Notenstufe (z.B. 2,0 statt 2,3) erhält, wer am Ende der Vorlesung mindestens 50% der Übungspunkte erhalten hat. Es gibt einmalig die Möglichkeit 10 Punkte durch Vorrechnen einer Aufgabe in den Übungsgruppen zu erhalten.

Prüfungen

  • Für Studierende des Bachelor-Studiengangs "Angewandte Informatik" (PO 2007) wird am Ende des nächsten Wintersemesters eine mündliche Prüfung des Moduls "Theoretische Informatik" (in Kombination mit "Berechenbarkeit und Komplexität") stattfinden. Studenten im ersten Semester, die im nächsten Semester nicht "Berechenbarkeit und Komplexität" hören werden, können bereits dieses Semester eine mündliche Prüfung in "Automaten und formale Sprachen" ablegen. Studierende nach der neuen Prüfungsordnung (PO 2012) können in "Automaten und formale Sprachen" auch eine schriftliche Prüfung ablegen.
  • 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.
  • Die Ergebnisse der zweiten Klausur Automaten und formale Sprachen vom 11.03.2016 sind nun verfügbar und können hier eingesehen werden. Bitte beachten Sie, dass auf Grund der geringen Zahl an Teilnehmern zur Wahrung der Anonymität einige fiktionale KIC zu der Liste hinzugefügt wurden. Sollten Sie eine Klausur-Einsicht wünschen, so setzen Sie sich bitte mit Sebastian Küpper in Kontakt um einen persönlichen Termin zu vereinbaren.

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.

Termine

Vorlesung:

  • Di, 12–14, LB 131

Die Vorlesung beginnt am Dienstag, den 7. April.

Übungen (finale Termine):

  • Di, 8-10, LE 120, Gruppe ISE (Englisch)
  • Di, 16-18, LK 061, Gruppe BAI-1 (Deutsch)
  • Do, 14-16, BC 523, Gruppe BAI-2 (Deutsch)
  • Fr, 10-12, LC 137, Gruppe BAI-3 (Deutsch)
  • Fr, 12-14, LK 052, Gruppe BAI-4 (Deutsch)

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

Am 1. Mai fallen die Gruppen BAI-3 und BAI-4 aus. Wir bieten dazu einen Ersatztermin am 30. April von 16-18 Uhr im Raum LC 137 an und bitten die Studierenden sich auf diese oder eine andere Übungsgruppe zu verteilen.

Am 14. Mai fällt die Gruppe BAI-2 aus. Wir bitten die Studierenden, sich auf andere Gruppen zu verteilen.

Am 26. Mai, sowie dem 4.-5. Juni fallen Vorlesung und Übungen aus.

AfS Klausur WS 2015/16:

  • Datum: 11. März
  • Zeit: 14 Uhr
  • Raum: LB 137

Mündliche Einzel- und Modulprüfungen WS 2015/16:

  • Zeitraum: 29. Februar - 4. März
  • Raum: LF 264

Aktuelles

no news in this list.

© Universität Duisburg-Essen, Lehrstuhl Theoretische InformatikLogin