Seminar: Automatentheorie und formale Sprachen
SoSe 2009 (Ankündigung)
Organisatorisches
Dozentin: Wiebke Petersen
Sitzung: Mi. 11-13; 23.21.04.87;
Sprechstunde: Mi. 16:30-17:30; 23.21.04.45;
Telefon: 81-15295
Literaturempfehlung
- Barbara H. Partee et al.: Mathematical Methods in Linguistics, Part E. Dordrecht et al.: Kluwer Acad. Publ., 1990.
- Ralf Klabunde: Formale Grundlagen der Linguistik. Tübingen: Gunter Narr Verlag, 1998. (Errata)
Sitzungen
| Datum | Thema | Literatur |
|---|---|---|
| 15.04.2009 | Vorbesprechung | |
| 22.04.2009 | Einführung | Folien  |
29.04.2009 | Mengen, Alphabete, Wörter, formale Sprachen | Folien |
06.05.2009 | reguläre Ausdrücke | Folien |
13.05.2009 | endliche Automaten (lesen sie bitte zur Vorbereitung der nächsten Sitzung Klabunde 1998, S. 62-62 ) |
Folien |
20.05.2009 | Übungen zu endliche Automaten | Exorciser | 27.05.2009 | endliche Automaten: Äquivalenzsätze | Folien |
03.06.2009 | endliche Automaten: Satz von Kleene (eine besonders gelungene Hausaufgabe finden sie hier ) |
Folien |
10.06.2009 | endliche Automaten: Pumpinglemma (Hinweise für die Anwendung des Pumpinglemmas finden sie hier ) |
Folien |
17.06.2009 | rechtslineare Grammatiken | Folien |
24.06.2009 | kontextfreie Sprachen und Grammatiken | Folien |
01.07.2009 | Pumpinglemma für kontextfreie Sprachen (Klabunde 1998 zum Pumping Lemma ) |
Folien |
08.07.2009 | Chomskyhierarchie, Kellerautomaten
Musterlösungen |
Folien |
15.07.2009 | Entscheidbarkeitsprobleme, endliche Transduktoren, Komplexität natürlicher Sprachen | Folien |
22.07.2009 | Klausurtermin (bitte beachten: die Klausur wird in Raum 23.11.03.22 geschrieben) |
Klausurergebnisse
Herzlichen Glückwunsch, alle haben bestanden! Hier die Ergebnisse im Einzelnen
Gruppenarbeiten und sonstiges
- Konstruktion eines deterministischen Automatens aus einem nichtdeterministischen nach Klabunde 1998 (Gruppe 1)
- effziente Konstruktion eines deterministischen Automatens aus einem nichtdeterministischen (Gruppe 2)
- Eliminierung von ε-Übergängen (Gruppe 3) und Abschlusseigenschaften von regulären Sprachen (Gruppe 4)
- Hinweise für die Anwendung des Pumpinglemmas
- zusätzliche Übungsaufgaben zu regulären Sprachen ( Musterlösung zur Aufgabe 9 )
Übungstermine (freiwillig)
- Montag, 13.7. um 14 Uhr in meinem Büro
- Freitag, 17.7. um 14 Uhr in meinem Büro
Zum Betrachten der Dateien benötigen sie Acrobat Reader.