Formale Sprachen und Automatentheorie
Formale Sprachen und Automatentheorie
 Allgemeines/Ankündigungen |
Kurzbeschreibung |
|
| Material zur Vorlesung |
Übungsblätter |
Literatur |
Die Seite mit Material zu FSA-HT01 ist nun hier.
Die Seite mit Material zu FSA-HT03 ist nun hier.
Allgemeines:
Stundentausch:
Mittwoch, 6.10.04, 11 h: (statt Übung) Vorlesung
(Raum 0301)
Mittwoch, 15.12.04, 10 h: (statt Vorlesung) Übung.
(verlegt auf: DO 16.12.04, 8-10)
MI künftig: Beginn der Vorlesung 10:10, Beginn der Übung 11:05
Nächste Sprechstunde zu GThI04/FSA04:
Mo, 11.4.05, 15 Uhr, voraussichtlich Raum 41 / 1414
Anmeldung per Email (zur Abschätzung von Zeit- und Raumbedarf) bis 8.4.05 erforderlich!
Material zur Vorlesung:
Hier sind künftig die in der Vorlesung verwendeten Folien zu
finden.
Diese allein ergeben noch kein vollständiges Skript!!!!
Übungen:
Das erste Übungsblatt wird am 6.10. ausgegeben. Die erste Übungsstunde
findet am 13.10. statt.
| Gruppe 1 | Polanski | Raum 0301 |
| Gruppe 2 | Iwan | Raum 2401 |
Hier sind künftig die Übungsblätter zu finden (Ausgabe jeweils MI).
 Übungsblatt 1 |
Übungsblatt 2 |
Übungsblatt 3 |
| Übungsblatt 4 |
Übungsblatt 5 |
Übungsblatt 6 |
| Übungsblatt 7 |
Übungsblatt 8 |
Übungsblatt 9 Korrektur: In Aufgabe 20 ist die Produktion S -> e zu ergänzen. |
| Übungsblatt 10/11 |
||
| Zur Wiederholung: | ||
| GThI/FSA - 1 | GThI/FSA - 2 | siehe auch: GThI-Seite |
 DVP-Klausur Januar 2005 |
Literatur:
- Schöning. Theoretische Informatik - kurzgefaßt. Spektrum Akademischer Verlag, 3. Auflage 1997.
- Hopcroft, Motwani, Ullman. Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. Pearson Studium, 2. Auflage, 2002.
- Hopcroft, Ullman. Introduction to automata theory, languages and computation. Addison-Wesley 1979.
Kurzbeschreibung:
Gegenstand dieser Vorlesung ist die Theorie der Chomsky-Sprachklassen und der zugehörigen Automatenbegriffe, wobei der Schwerpunkt auf regulären und kontextfreien Sprachen liegt.
Inhalte sind insbesondere:
- Die Hierarchie der Chomsky-Sprachklassen: Grammatikklassen und Akzeptoren, Abschlußeigenschaften
- Reguläre Sprachen: Chomsky-3-Grammatiken, deterministische und nichtdeterministische endliche Automaten, reguläre Ausdrücke, Konstruktion von Minimalautomaten, Satz von Myhill-Nerode, Pumping-Lemma für reguläre Sprachen, Entscheidbarkeitsfragen
- Kontextfreie Sprachen: Chomsky-2-Grammatiken, Kellerautomaten, Umformungen für Grammatiken und Normalformen (insbesondere Chomsky-Normalform und Greibach-Normalform), Pumping-Lemma für kontextfreie Sprachen, CYK-Algorithmus, Entscheidbarkeitsfragen
Weitere Informationen zu Lehrveranstaltungen unseres
Instituts
Institut für Theoretische Informatik und
Mathematik
Birgit Elbl
