Automata and Formal Languages

Worum geht's

Du lernst, wie verschiedene Klassen von Automaten (endliche, deterministische, nichtdeterministische, Büchi-Automaten) als Datenstrukturen zur Darstellung und Manipulation von (auch unendlichen) Mengen und Relationen eingesetzt werden. Du übst Aufbau und Kombination von Automaten, automatische Operationen (z. B. Boolesche Operationen, Joins) und den Zusammenhang zwischen Automaten und Logik sowie deren Anwendung in Pattern-Matching, Program Verification und bei Problemen wie Diophantischen Gleichungen.

Was du danach kannst

Finite Automaten als Datenstruktur für endliche und unendliche Mengen verwenden
Komplexität verschiedener Operationen für unterschiedliche Automatenklassen einschätzen
Zwischen logischen und automaten-theoretischen Beschreibungen übersetzen
Automatenmethoden auf Pattern-Matching und formale Verifikation anwenden

Aus was das Modul besteht

VorlesungVermittlung der Theorie, Vorstellung von Algorithmen und Einsatzgebieten; interaktive Kurzübungen während der Vorlesung
TutoriumDiskussion und Besprechung der wöchentlichen Übungsaufgaben

Lehrmethode

Vorlesung mit Online-Kurzaufgabenführt schrittweise durch die Inhalte und festigt Wissen durch aktive Teilnahme
Wöchentliche schriftliche Aufgabenermöglichen vertieftes Üben, deren Lösungen werden in den Tutorien besprochen
Tool-Präsentationenzeigen praktische Umsetzung und Anwendung der Algorithmen

Solltest du schon können

IN0011 Introduction to Theory of Computationempfohlen

Prüfung

KlausurschriftlichÜbungsaufgaben

Klausur, 120 Minuten. Die Prüfung besteht aus einer Liste von Übungen: Konstruktion von Automaten für Sprachen (direkt oder über Komposition), Anwendung und Kombination von Algorithmen zur Übersetzung zwischen Logik und Automaten sowie Auswahl geeigneter automaten-theoretischer Techniken zur Lösung von Verifikations- und Pattern-Matching-Problemen.

Prüfungstermin18.02. · 14:00–16:0000.02.001, MI HS 1, Friedrich L. Bauer Hörsaal (5602.EG.001)

Literatur

Javier Esparza - Automata Theory: An algorithmic approach (Lecture notes, 2012)
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman - Introduction to Automata Theory, Languages and Computation (3rd ed., 2006)
Joerg Flum, Erich Graedel, Thomas Wilke (eds.) - Logic and Automata: History and Perspectives, Volume 2 (2008)
Dominique Perrin, Jean-Éric Pin - Infinite Words: Automata, Semigroups, Logic and Games (2004)

Termine

Vorlesung mit ÜbungAutomaten und formale Sprachen (IN2041)3 Gruppen zur Wahl

ADi.10:30–12:30
00.04.011, MI Hörsaal 2 (5604.EG.011)
14× · 13.10.–02.02.
- 13.10.
- 20.10.
- 27.10.
- 03.11.
- 17.11.
- 24.11.
- 01.12.
- 08.12.
- 15.12.
- 22.12.
- 12.01.
- 19.01.
- 26.01.
- 02.02.
BDo.14:00–16:00
02.13.010, Seminarraum (5613.02.010)
14× · 15.10.–04.02.
- 15.10.
- 22.10.
- 29.10.
- 05.11.
- 12.11.
- 19.11.
- 26.11.
- 10.12.
- 17.12.
- 07.01.
- 14.01.
- 21.01.
- 28.01.
- 04.02.
CMi.08:00–10:00
00.5901.051, Hörsaal (5901.EG.051)
15× · 14.10.–03.02.
- 14.10.
- 21.10.
- 28.10.
- 04.11.
- 11.11.
- 18.11.
- 25.11.
- 02.12.
- 09.12.
- 16.12.
- 23.12.
- 13.01.
- 20.01.
- 27.01.
- 03.02.

Aus dem laufenden Semester, unverbindlich. Von mehreren Gruppen besucht man eine; der Stundenplan schlägt automatisch die mit den wenigsten Überschneidungen vor.

Filter