LEA

Automaten und Formale Sprachen

Aktuelles

    Die Klausureinsicht findet am Montag den 23.02.2015 zwischen 10:00 und 12:00 Uhr in Raum 03.09.037 statt. Bitte schreiben Sie eine Mail an Moritz Fuchs wenn Sie vorhaben zu kommen.

Vorlesung

  • Dozent:
    Prof. Dr. Ernst W. Mayr
  • Modul: IN2041
  • Bereich:
    4+2 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik)
  • ECTS: 8 Punkte
  • Zeit und Ort:
    Dienstag, 08:30–10:00, 00.13.009A
    Freitag, 10:15–11:45, 00.13.009A
  • Übung:
    2 SWS Übung zur Vorlesung
    Dienstag, 12:15–13:45, 03.11.018
    Übungsleitung: Moritz Fuchs
  • Klausurtermine:
    Abschlussklausur: Mittwoch, 11. Februar 2015, 11:30 - 14:30 Uhr Hörsaal MI HS3
    Wiederholungsprüfung (mündlich): Freitag, 10. April 2015 ab 9 Uhr in Raum MI 03.09.054 Falls Sie an der Wiederholungsprüfung teilnehmen möchten, tragen Sie sich in TUMonline bis zum 21.03.2015 ein!

    Als Hilfsmittel ist jeweils nur ein beidseitig eigenhändig beschriebenes A4-Blatt mit Notizen zugelassen.
  • Erfolgreiche Teilnahme:
    Für das Bestehen des Moduls ist die erfolgreiche Teilnahme an der Abschlussklausur (Endterm) erforderlich.
    Die Erfahrungen der letzten Jahre legen nahe, dass es für die erfolgreiche Bearbeitung der Klausur(en) sehr förderlich ist, die angebotenen Hausaufgabenblätter zu bearbeiten (Sie erhalten sie korrigiert zurück) und auch an der Übung teilzunehmen!
  • Zielgruppe:
    Studierende im Hauptstudium der Informatik
    Studierende mit Nebenfach Informatik
  • Voraussetzungen:
    Stoff des Informatik-Grundstudiums, insbesondere die THEO Vorlesung
  • Sprechstunde:
    siehe hier

Inhalt

Automaten auf endlichen Worten
  • Automaten-Klassen und Umwandlungen
    • Reguläre Ausdrücke, deterministische und nicht-deterministische Automaten
    • Umwandlungsalgorithmen
  • Minimierung und Reduzierung
    • Minimierung von DFAs
    • Reduzierung von NFAs
  • Boolesche Operationen und Tests
    • Implementation auf DFAs
      • Zugehörigkeit, Komplement, Vereinigung, Schnitt, Leerheit, Universalität, Einschluss, Gleichheit
      • Implementation auf NFAs
  • Operationen auf Relationen
    • Projektion, join, post, pre
  • Operationen auf endlichen Universen: Entscheidungsdiagramme
  • Automaten und Logik
  • Anwendungen: Pattern-matching, Verifikation, Presburger Arithmetik

Automaten auf unendlichen Worten
  • Automaten-Klassen und Umwandlungen
    • Omega-reguläre Ausdrücke
    • Büchi-, Streett-, und Rabin-Automaten
  • Boolesche Operationen
    • Vereinigung und Schnitt
    • Komplement
  • Prüfung auf Leerheit
  • Anwendung: Verifikation mit Temporallogik

Folien