Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Logik in der Informatik

Vorlesung Automatentheorie

 

 

Aktuelles

 

  • Am Dienstag, den 1. Juli, findet leider keine Vorlesung statt.
  • Am 29.4., 2.5. und 30.5. findet keine Vorlesung statt. Zusätzlich entfallen am 2.5. und 30.5. die Übungstermine. Zu diesen Terminen wird dann auch kein neues Übungsblatt veröffentlicht; die Bearbeitungszeit der entsprechenden Übungsblätter verlängert sich dann auf 14 Tage.
  • Die Eröffnungsvorlesung fand am Dienstag, 15. April 2025, statt.

 

Einführung

 

Wir befassen uns in der Vorlesung mit der Theorie endlicher Automaten auf endlichen und unendlichen Wörtern, sowie auf Bäumen. Hierbei untersuchen wir verschiedene Typen von Automaten, deren Abschlusseigenschaften und Umwandlungsmöglichkeiten zwischen verschiedenen Modellen, verschiedene Entscheidungsprobleme (bspw. Leerheits- oder das Äquivalenzproblem) und deren Beziehungen zu verschiedenen Logiken wie LTL, CTL und MSO.

 

Logbuch

 

Im Logbuch finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungsstunden, Teile des Vorlesungsskripts und gelegentlich auch Korrekturen und sonstige ergänzende Bemerkungen.

 

Termine

Vorlesung
Dienstags 15:00-17:00 im ESZ (Rudower Chaussee 26), Raum 1'306
Freitags 11:00-13:00 im ESZ (Rudower Chaussee 26), Raum 1'306

Dozent: Dr. André Frochaux

Die Eröffnungsvorlesung findet am 15.04.25 statt.

Übung
Freitags 13:00-15:00 im ESZ (Rudower Chaussee 26), Raum 1'306

Übungsleiter: Benjamin Hauskeller

Die erste Übungsstunde findet am 25.04.24 statt.

Übungsblätter

 

Ab der zweiten Vorlesungswoche wird wöchentlich, jeweils freitags ein Übungsblatt hier und im Moodle-Kurs online bereitgestellt.

  • Blatt 1 (bereitgestellt am 25.04., Bearbeitung bis zum 09.05., 12:45 Uhr)
  • Blatt 2 (bereitgestellt am 9.05., Bearbeitung bis zum 16.05., 12:45 Uhr)
  • Blatt 3 (bereitgestellt am 16.05., Bearbeitung bis zum 23.05., 12:45 Uhr)
  • Blatt 4 (bereitgestellt am 23.05., Bearbeitung bis zum 6.06., 12:45 Uhr)
  • Blatt 5 (bereitgestellt am 6.06., Bearbeitung bis zum 13.06., 12:45 Uhr)
  • Blatt 6 (bereitgestellt am 13.06., Bearbeitung bis zum 20.06., 12:45 Uhr)
  • Blatt 7 (bereitgestellt am 20.06., Bearbeitung bis zum 27.06., 12:45 Uhr)
  • Blatt 8 (bereitgestellt am 27.06., Bearbeitung bis zum 4.07., 12:45 Uhr)
  • Blatt 9 (bereitgestellt am 4.07., Bearbeitung bis zum 11.07., 12:45 Uhr)

Verbindliche "Spielregeln" zum Erwerb von Übungspunkten

Sie können bei jedem Übungsblatt entscheiden, gemäß welcher der folgenden beiden Varianten A bzw. B Ihre Lösung bewertet werden soll:

Variante A:

Sie geben eine schriftliche, ausführlich ausgearbeitete und mathematisch präzise Lösung spätestens direkt vor Beginn der Übungsstunde am Freitag ab. Die Abgabe erfolgt entweder direkt zu Beginn der Übungsstunde beim Übungsleiter oder wird bis Freitag 12:45 Uhr in den Briefkasten am Lehrstuhl (RUD25 zwischen den Räumen 3.401 und 3.402) eingeworfen.

Variante B:

Sie geben keine Lösung ab. Stattdessen tragen Sie direkt vor Beginn der Übung in einer bereitgestellten Liste ein, wie viele Übungspunkte Sie für Ihre Lösung der einzelnen Aufgaben[teile] für gerechtfertigt halten. Während der Übungsstunde werden aus dieser Liste einzelne Teilnehmer zum Vorrechnen von Aufgaben[teilen] ausgesucht. Falls sich beim Vorrechnen herausstellen sollte, dass Sie keine sinnvolle Lösung vorweisen können, obwohl Sie in der Liste Punkte für diese[n] Aufgabe[nteil] eingetragen haben, werden Ihnen für das gesamte gerade behandelte Übungsblatt keine Übungspunkte angerechnet. Eine sinnvolle Lösung muss hierbei nicht notwendigerweise vollständig korrekt sein.

 

Prüfung

 

Zur Vorbereitung auf eine Prüfung (Modulabschlussprüfung) ist es unbedingt notwendig, das gesamte, in den Vorlesungs- und Übungsstunden behandelte Material durchzuarbeiten.

Die Modulabschlussprüfung wird durch eine mündliche Prüfung erfolgen. Details folgen im Laufe des Semesters.

Die Prüfungen finden am 28. und 30. Juli 2025 im Raum 3'408 RUD25 statt.

Voraussetzung für die Zulassung zur Prüfung ist:

  • Erreichen von mindestens 50 Prozent aller Übungspunkte. Um dies zu gewährleisten, empfehlen wir dringend, regelmäßig und aktiv an den Übungsstunden teilzunehmen. Beachten Sie hierzu auch die "Spielregeln" -- und
  • Erreichen von mindestens 40 Prozent der Punkte eines gesonderten Präsenzübungsblattes, welches in der Mitte des Semesters bearbeitet wird. TRUE

 

Hinweise zur Prüfungsanmeldung

  1. Die Modulabschlussprüfung (kurz: MAP) wird als mündliche Prüfung durchgeführt. Dafür müssen Sie sich in AGNES anmelden – die Frist für die Anmeldung zum 1. Prüfungszeitraum endet am 30. Juni 2025! Für jeden Prüfungstag gibt es eine separaten Eintrag. Melden Sie sich nur für einen der Tage an. Sie können sich auch anmelden, falls Sie die Voraussetzung zur Zulassung zur MAP zum jetzigen Zeitpunkt noch nicht erfüllen. Sollten Sie die Zulassung bis zum 14.7.25 nicht besitzen, werden Sie automatisch wieder abgemeldet (ohne dass dadurch Nachteile für Sie entstehen) und Sie werden in diesem Fall darüber über die in Agnes hinterlegte Mail informiert. Umgekehrt ist der 30. Juni 2025 eine harte Frist: Danach ist für den ersten Prüfungszeitraum keine Anmeldung mehr möglich!
  2. Zusätzlich zu der Anmeldung über Agnes benötigen Sie eine konkrete Prüfungszeit. Melden Sie sich dazu direkt nach Ihrer Anmeldung in Agnes per Mail an Silvia Schoch mit André Frochaux in cc. Nutzen Sie hierfür Ihre offizielle HU-Mail (CMS-Account), wählen Sie als Betreff: "Prüfung: Automatentheorie" und geben Sie Ihren Namen, Ihre Matrikelnummer und den in Agnes ausgewählten Prüfungstag an und bitten um die Zuteilung einer Prüfungszeit. Wichtig: zur Durchführung der MAP ist beides nötig: fristgerechte Anmeldung in AGNES und Vereinbarung einer konkreten Prüfungszeit.

 

Literatur

 

[1] John E. Hopcroft und Jeffrey D. Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheotrie. Addison-Wesley, 1993.
[2] Javier Esparza und Michael Blondin: Automata Theory: An Algorithmic Approach. MIT Press, 2023.
[3] Dominique Perrin und Jean-Éric Pin: Infinite Words: Automata, Semigroups, Logic and Games. Academic Press, 2004.
[4] Martin Hofmann und Martin Lange: Automatentheorie und Logik. Springer, 2011.
[5] Hubert Comon et al.: Tree Automata Techniques and Applications. Online verfügbar: http://tata.gforge.inria.fr/
[6] Edmund M. Clarke, Orna Grumberg und Doron A. Peled: Model Checking. MIT Press, 2001.
[7] Jean-Éric Pin: Mathematical Foundations of Automata Theory. Online verfügbar: https://www.irif.fr/~jep/PDF/MPRI/MPRI.pdf
[8] Howard Straubing: Model Checking: Finite Automata, Formal Logic, and Circuit Complexity. Birkhäuser Boston, MA, 1994.