Proseminar "Automaten, Grammatiken und ihre Anwendungen"

» Diese Veranstaltung wird auf deutsch gehalten.

Proseminar im Wintersemester 2009/2010

ArtTermine/OrtBeginnVeranstalter
PS2 Termine nach Vereinbarung Thomas

Inhalt

Das Proseminar schließt an die Vorlesung Formale Systeme, Automaten, Prozesse an. Es werden Themen im Bereich der regulären, kontextfeien und kontextsensitiven Sprachen vertieft und Anwendungen studiert. Stichworte zu den Themen sind

  • Deterministische kontextfreie Sprachen
  • Mehrdeutigkeit in kontextfreien Grammatiken
  • Parsing für kontextfreie Grammatiken
  • Kontextsensitive Sprachen und Automaten

Neben der Erarbeitung der Inhalte sind die Strukturierung des Stoffes, die kompetente Präsentation (schriftlich und im Vortrag) und die Literaturrecherche ein wesentlicher Bestandteil des Proseminars.

Organisatorisches

Generelle Informationen zum Ablauf finden Sie auf den Folien aus der Vorbesprechung.

Wichtige Termine:

  • Am Mitwoch, 14.10.2009 um 14 Uhr: Veranstaltung zum Vorbereiten und Gestalten von Vorträgen (Folien)
  • Nehmen Sie bis spätestens zum 23.10.2009 Kontakt mit Ihrem Betreuer auf.
  • Die Frist für die Abgabe der Ausarbeitung ist der 4.12. 2009
  • Das Proseminar soll am 8. und 11. Januar 2010 stattfinden. Kollisionen mit anderen Veranstaltungen mit Anwesenheitspflicht melden Sie bitte an Christof Löding

Bei Fragen zum Ablauf wenden Sie sich an Ihren Betreuer (siehe unten) oder an Christof Löding.

Vorträge

Das Proseminar wird in 2 Blöcken folgenden Tagen stattfinden:

  • Freitag 8.1.10 von 8:20 bis 11:30 Uhr
  • Montag 11.1.10 von 9:00 bis 15:00 Uhr

Die genauen Zeiten für die Vorträge sind unten angegeben.

Die Vorträge finden im Seminarraum am Lehrstuhl 7 statt.

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

Vorträge am Freitag, 8.1.10:

Von 9:00-9:45 Uhr
  • Umformungen für reguläre Ausdrücke
    Quelle: [HMU,3.4]
    Vortrag: Jan Gossens
    Betreuung: M. Slaats
  • XML und DTDs
    Quelle:[Rich,Q.1.2; HMU,5.3.4]
    Vortrag: entfällt
    Betreuung: M. Slaats
Von 10:00-11:30 Uhr
  • Mehrdeutige Grammatiken
    Quelle: [Rich,11.7]
    Vortrag: Claude Mangen
    Betreuung: M. Slaats
  • Odgens Lemma
    Quelle: [Rich,13.6]
    Vortrag: Dupleix Takoulegha
    Betreuung: C. Löding

Vorträge am Montag, 11.1.10:

Von 9:00-10:30 Uhr
  • Satz von Parikh
    Quelle:[Rich,13.7+D.3]
    Vortrag: Maren Kuschay
    Betreuung: C. Löding
  • Top-Down Parsing
    Quelle: [Rich,15.2.1 und 15.2.2]
    Vortrag: Jan Rappen
    Betreuung: D. Neider
Von 10:45-12:15 Uhr
  • Deterministisches Top-Down Parsing mit LL(1)-Grammatiken
    Quelle: [Rich,15.2.3]
    Vortrag: Roman Haag
    Betreuung: D. Neider
  • Bottom-Up Parsing
    Quelle: [Rich,15.3]
    Vortrag: Walter Weber
    Betreuung: D. Neider
Von 13:30-15:00 Uhr
  • Der Earley Algorithmus
    Quelle: [Rich,15.4.2]
    Vortrag: Christoph Hommelsheim
    Betreuung: D. Neider
  • Kontextsensitive Sprachen und linear beschränkte Automaten
    Quelle: [Rich,24.1]
    Vortrag: Benjamin Meister
    Betreuung: C. Löding

Quellen

[Rich] Rich, Elaine: Automata, computability, and complexity - Theory and applications. Pearson, 2008.
[HMU] Hopcroft, John E. / Motwani, Rajeev / Ullman, Jeffrey D.: Introduction to automata theory, languages, and computation. Addison-Wesley, 2. Auflage, 2001.