Proseminar Automatentheorie

» Diese Veranstaltung wird auf deutsch gehalten.

Proseminar im Wintersemester 2013/2014

Veranstalter

Lehrstuhl Informatik 7, Christof Löding

Inhalt

In diesem Proseminar werden weiterführende Themen im Anschluss an die Vorlesung Formale Systeme, Automaten, Prozesse behandelt. Die genaue Auswahl der Themen wird sich nach der Anzahl der Teilnehmer richten. Für Themenbeispiele siehe die Webseite des Proseminars vom letzten Jahr.

Neben der Erarbeitung der Inhalte tritt mit gleichem Gewicht das Training in der Literatur-Recherche, der Strukturierung des Stoffes und der kompetenten Präsentation (schriftlich und im Vortrag).

Organisatorisches

Die Vergabe der Plätze erfolgt über das zentrale Vergabeverfahren.

Informationen zum Ablauf des Proseminars findet man auf den Folien aus der Vorbesprechung

Bei Fragen wenden Sie sich bitte an Christof Löding.

Termine

  • Laut Prüfungsordnung haben Sie nach der Vorbesprechung 3 Wochen, um sich vom Seminar abzumelden (ohne einen Fehlversuch angerechnet zu bekommen). Danach wir die Anmeldung verbindlich.
  • Die Vorträge des Proseminars werden semesterbegleitend dienstags von 16:15-17:30 Uhr im Seminarraum am Lehrstuhl 7 stattfinden (siehe unten für die Liste der Termine und Themen). Normalerweise finden zwei Vorträge pro Termin statt. Am letzten Termin sind 3 Vorträge geplant.
  • Veranstaltung mit Hinweisen zur Ausarbeitung sowie zum Vorbereiten und Halten von Vorträgen in der ersten Vorlesungswoche: Dienstag, 15.10.2013, 16-17 Uhr, Seminarraum Informatik 7. Folien aus der Veranstaltung
  • Erste Besprechung mit Betreuer spätestens 6 Wochen vor dem Vortragstermin (Sie müssen sich beim Betreuer melden). Sie sollten sich möglichst früh melden, um abzuklären, wo die Schwerpunkte gesetzt werden sollen.
  • Abgabe der Ausarbeitung bis spätestens 2 Wochen vor dem Vortragstermin (oder nach Absprache mit Betreuer).

    Themen

      12. November 2013
    1. Das Komplementproblem für DPDAs
      Quelle: [HU79,10.2]
      Vortrag: Pascal Stump
      Betreuung: S. Repke
    2. Ogdens Lemma
      Quelle: [Rich,13.6], [HU79,6.1]
      Vortrag: Sandra-Jasmin Petrut
      Betreuung: S. Repke

      3. 19. November 2013
    3. Greibach Normalform
      Quelle: [Rich,11.8,D.1], [Kozen,21]
      Vortrag: Eva Fluck
      Betreuung: S. Repke
    4. Satz von Chomsky und Schützenberger
      Quelle:[Kozen,G]
      Vortrag: Lukas Huwald
      Betreuung: S. Repke

      5. 26. November 2013
    5. Lineare Sprachen
      Quelle: [Harrison,6.8]
      Vortrag: Sebastian Hueber
      Betreuung: M. Lang
    6. Mehrdeutige Grammatiken
      Quelle: [Rich,11.7], [HU79,4.7]
      Vortrag: Julia Barth
      Betreuung: M. Lang

      7. 3. Dezember 2013
    7. LR(0)-Grammatiken und DPDAs
      Quelle: [HU79,10.6]
      Vortrag: entfällt
      Betreuung: M. Lang
    8. Lindenmayer-Systeme
      Quelle: [Rich,24.4]
      Vortrag: Christopher Hugenroth
      Betreuung: M. Lang

      9. 10. Dezember 2013
    9. Typ-0-Sprachen und Turingmaschinen
      Quelle: [Rich,23.1 und 23.2], [HU69,7.5]
      Vortrag: Bernd Hankammer
      Betreuung: M. Lang
    10. Satz von Parikh
      Quelle:[Rich,13.7+D.3], [Kozen,H]
      Vortrag: Florian Lahr
      Betreuung: M. Lang

      11. 17. Dezember 2013
    11. Vier-Wege-Automaten
      Quelle: [BH67]
      Vortrag: Lukas Westhofen
      Betreuung: M. Lang

      12. 14. Januar 2014
    12. Zwei-Wege-Automaten
      Quelle: [HU79,2.6]
      Vortrag: David Rath
      Betreuung: M. Lang
    13. Umformungen für reguläre Ausdrücke
      Quelle: [HMU,3.4]
      Vortrag: Daniel Schuster
      Betreuung: C. Löding
    14. Erweiterte Abschlusseigenschaften regulärer Sprachen (Substitutionen und Homomorphismen)
      Quelle: [HU79,3.2], [HMU,4.2.3 und 4.2.4]
      Vortrag: Niklas Rieken
      Betreuung: C. Löding

      15. 21. Januar 2014
    15. Co-Determinismus und Minimierung durch Determinisierung
      Quelle: [Sakarovitch,3.3.4]
      Vortrag: Timon Noethlichs
      Betreuung: C. Löding
    16. Zustandszusammenfassung für nichtdeterministische Automaten
      Quelle: [Kozen,B]
      Vortrag: Ömer Sali
      Betreuung: C. Löding

      17. 28. Januar 2014
    17. Automaten mit Gleichungen
      Quelle: [KN01]
      Vortrag: Lukas Armborst
      Betreuung: C. Löding
    18. Automaten mit Ausgabe: Einführung und Minimierung
      Quelle: [Kohavi,10-1 und 10-3]
      Vortrag: Maria Theißen
      Betreuung: C. Löding
    19. Minimierung unvollständig spezifizierter Automaten mit Ausgabe
      Quelle: [Kohavi,10-4] und evtl. [Pfleeger73]
      Vortrag: Steffen Fündgens
      Betreuung: C. Löding

Quellen

[BH67] Blum, M./ Hewitt, C.: Automata on a 2-dimensional tape. Proc. 8th IEEE Symp. on Switching and Automata Theory, 155-167, 1967.
[Harrison] Harrison, Michael A.: Introduction to Formal Language Theory. Addison-Wesley, 1978.
[HMU] Hopcroft, John E. / Motwani, Rajeev / Ullman, Jeffrey D.: Introduction to automata theory, languages, and computation. Addison-Wesley, 2. Auflage, 2001.
[HU69] Hopcroft, John E. / Ullman, Jeffrey D.: Formal Languages and their Relation to Automata. Addison-Wesley, 1969.
[HU79] Hopcroft, John E. / Ullman, Jeffrey D.: Introduction to automata theory, languages, and computation. Addison-Wesley, 1979.
[Kohavi] Kohavi, Zvi: Switching and Finite Automata Theory. McGraw-Hill 1970.
[KN01] Khoussainov, Bakhadyr/ Nerode, Anil: Automata Theory and its Applications Birkhäuser 2001.
[Kozen] Kozen, Dexter: Automata and Computability. Springer 1997.
[MKA] Skript zur Vorlesung Modelle und Konstruktionen der Automatentheorie, W. Thomas, 1999. Link
[Pfleeger73] Pfleeger, Charles P.: State Reduction in Incompletely Specified Finite-State Machines. IEEE Transactions on Computers, vol. C-22(12), 1973, pp. 87--106, 1973.
[Rich] Rich, Elaine: Automata, computability, and complexity - Theory and applications. Pearson, 2008.
[Sakarovitch] Sakarovitch, Jacques: Elements of Automata Theory. Cambridge University Press, 2009.