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