Automatentheorie und formale Sprachen
SoSe 10 (Ankündigung)
Organisatorisches
Dozentin: Wiebke Petersen
Sitzungen: Mo. 14-16 Uhr in Raum 25.22.U1.34
Sprechstunde: Do. 16:00-17:00 in Raum 23.21.04.45
Telefon: 81-15295
Literaturempfehlung
- B. H. Partee et al. (1990): Mathematical Methods in Linguistics. Kluwer Acad. Publ.
- R. Klabunde (1998): Formale Grundlagen der Linguistik. Narr Verlag.
- U. Schöning (5. Aufl., 2008): Theoretische Informatik - kurzgefasst. Spektrum.
- J. E. Hopcroft; R. Motwani; J. D. Ullman (2. Aufl., 2002): Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Addison-Wesley Longman Verlag.
Organisatorisches
Aufgaben
Sitzungen
| Datum | Thema | Literatur | Folien / Hausaufgaben |
|---|---|---|---|
| 12.4.2010 | Vorbesprechung | ||
| 19.4.2010 | Mengen und Sprachen | Schöning (Anhang) | |
| 26.4.2010 | Relationen und Funktionen | Schöning (Anhang) bis Seite 179 einschließlich | Aufgabe |
| 3.5.2010 | endliche Automaten | Schöning (Kap. 1.2.1) | |
| 10.5.2010 | nichtdeterministische Automaten | Schöning (Kap. 1.2.2) | |
| 17.5.2010 | Chomsky Hierarchie | Schöning (Kap. 1.1.1-1.1.2) | |
| 24.5.2010 | fällt aus: Feiertag | ||
| 31.5.2010 | Typ3 Grammatiken und endliche Automaten | Schöning (S. 22, S. 27) | |
| 7.6.2010 | reguläre Ausdrücke und endliche Automaten | Schöning (Kap. 1.2.3) | |
| 14.6.2010 | Satz von Myhill Nerode | Schöning (Kap. 1.2.5) | siehe gesonderte Aufgabenliste oben |
| 21.6.2010 | Minimierung endlicher Automaten | Schöning (Kap. 1.2.5) | |
| 28.6.2010 | kontextfreie Grammatiken und Chomsky-Normalform | Schöning (Kap. 1.3.1) | |
| 5.7.2010 | Pumpinglemma für kontextfreie Sprachen | Schöning (Kap. 1.3.2) | |
| 12.7.2010 | Turingmaschinen, Entscheidbarkeit und Berechenbarkeit | Schöning (Kap. 2) | empfehlenswerte Einführung in Turingmaschinen |
| 19.7.2010 | formale Sprachen und nicht entscheidbare Probleme | Schöning (Kap. 2) |