Automatentheorie und formale Sprachen
SoSe 11 (Ankündigung)
Organisatorisches
Dozentin: Wiebke Petersen
Sitzungen: Mo. 14:30-16:00 Uhr in Raum 22.01.HS 2C
Sprechstunde: Mo. 16:30-18:00 in Raum 23.21.04.45
Telefon: 81-15295
Lektüre
- U. Schöning (5. Aufl., 2008): Theoretische Informatik - kurzgefasst. Spektrum.
zusätzliche Literaturempfehlungen
- K.-U. Carstensen et al. (2004): Computerlinguistik und Sprachtechnologie. Eine Einführung. Spektrum, Akademischer Verlag
- 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.
- D. Jurafsky & J. H. Martin (2008): Speech and Language Processing. An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition. Prentice Hall. 2nd Edition.
- R. Klabunde (1998): Formale Grundlagen der Linguistik. Narr Verlag.
- B. H. Partee et al. (1990): Mathematical Methods in Linguistics. Kluwer Acad. Publ.
- R. Socher (2005): Theoretische Grundlagen der Informatik. Fachbuchverlag Leipzig. 2. Auflage
Aufgaben
- Hinweise zur Scheinvergabe
- Aufgabenpaket 1
- Aufgabenpaket 2
- Aufgabenpaket 3
- Aufgabenpaket 4
- Aufgabenpaket 5
- Aufgabenpaket 6
- Aufgabenpaket 7
Sitzungen
| Datum | Thema | Literatur | Aufgaben |
|---|---|---|---|
| 4.4.2011 | Vorbesprechung | ||
| 11.4.2011 | Mengen und Relationen | Schöning (Anhang) | |
| 18.4.2011 | Äquivalenzrelationen und Funktionen | Schöning (Anhang) | Aufgabenpaket 1 (siehe oben) und lesen Sie bitte Schöning 1.1.1 und 1.1.2 |
| 25.4.2011 | fällt aus (Feiertag) | ||
| 2.5.2011 | Grammatiken und Chomskyhierarchie | Schöning (1.1.1 und 1.1.2), (Folie zur Chomskyhierarchie) | Aufgabenpaket 2 (siehe oben) und lesen Sie bitte Schöning 1.1.3-1.1.5 |
| 9.5.2011 | Entscheidbarkeit des Wortproblems für Typ1-Sprachen; Backus-Naur-Form; endliche Automaten | Schöning (1.1.3 - 1.1.5) | Aufgabenpaket 3 |
| 16.5.2011 | Umwandlung DFA in Typ3-Grammatik; Umwandlung DFA in NFA | Schöning (1.2.1 und 1.2.2) | |
| 23.5.2011 | Reguläre Ausdrücke; Satz von Kleene | Schöning (1.2.3-1.2.4) | Aufgabenpaket 4 |
| 30.5.2011 | Umwandlung: endliche Automaten in reguläre Ausdrücke; Pumpinglemma | ||
| 6.6.2011 | Äquivalenzrelationen und Minimalautomaten; Abschlußeigenschaften; Entscheidbarkeit | Schöning (1.2.5-1.2.7) | Aufgabenpaket 5 |
| 13.6.2011 | fällt aus (Feiertag) | ||
| 20.6.2011 | Kontextfreie Sprachen, Chomsky-Normalform, Baumhöhenlemma, Pumpinglemma für kontextfreie Sprachen | Schöning (1.3.1-1.3.2) | Aufgabenpaket 6 |
| 27.6.2011 | Typ1- und Typ0-Sprachen, Chomsky-Hierarchie: Abschlußeigenschaften, Entscheidbarkeitsprobleme | Schöning (1.4) | |
| 4.7.2011 | Berechenbarkeit | Schöning (2), (Folie zur Entscheidbarkeit; Onlinemodul zu Turingmaschinen; Turingmaschinen Beispiele) | Aufgabenpaket 7 |
| 11.7.2011 | formale Sprachen und nicht entscheidbare Probleme | Schöning (2) |