Mathematische Grundlagen: Formale Sprachen und Automaten
Vorlesung mit Übung
Leitung: | Dr. Stefan Thater |
Zeit und Ort: | siehe LSF |
Inhalt
Der Kurs vermittelt allgemeine Konzepte und Kenntnisse zu formalen Sprachen. Es werden verschiedene Typen von Automaten und formalen Grammatiken vorgestellt und ihre Beziehungen untereinander und zu den verschiedenen Typen von formalen Sprachen in der Chomsky-Hierarchie untersucht. Dabei legen wir besonderes Gewicht auf das Üben des praktischen und argumentativen Umgangs mit den verschiedenen Formalismen.
Thematisch gliedert sich der Kurs in drei Teile:
- Reguläre Sprachen: Reguläre Ausdrücke; deterministische endliche Automaten (DEA); nichtdeterministische Automaten (NEA); Äquivalenz von DEA und NEA; Äquivalenz von endlichen Automaten und regulären Sprachen; Pumping Lemma für reguläre Sprachen; deterministische endliche Transducer (1.–5. Woche)
- Kontextfreie Sprachen: Kontextfreie Grammatiken; Pumping Lemma für kontextfreie Sprachen; Kellerautomaten; Äquivalenz von kontextfreien Grammatiken und Kellerautomaten; Top-down und Bottom-up Parsing-Verfahren; deterministische Kellerautomaten (6.–9. Woche)
- Chomsky-Hierarchie: Typ-0 Sprachen; Turingmaschinen; die Universal-Turingmaschine; das Halteproblem für Turingmaschinen; Typ-0-Grammatiken und Turingmaschinen (10.–12. Woche)
Literatur
- Lewis, H. R., C. H. Papadimitriou, Elements of the Theory of Computation. New Jersey: Prentice Hall 1981.
- Hopcroft, J. E., J. D. Ullmann: Introduction to Automata Theory, Languages and Computation. Addison-Wesley 1979.
- Partee, B., A. ter Meulen, R. Wall, Mathematical Methods in Linguistics. Dordrecht: Kluwer 1990.
Voraussetzungen
Empfohlen: Mathematische Grundlagen: Logik
Prüfungsleistung
Die Prüfungsleistung besteht aus einer Klausur im Umfang von 90 Minuten. Informationen zum Klausur-Termin finden sich im Vorlesungsverzeichnis (LSF). Die Anmeldefrist endet eine Woche vor der Klausur. Zugelassenes Hilfsmittel ist ein Spickzettel
im Umfang von zwei DIN A4 Seiten (ein DIN A4 Blatt), den sich die Teilnehmer selbst zusammenstellen können.
Zu Beginn des kommenden Wintersemesters wird eine Wiederholungsprüfung (Nachklausur
, 90 Minuten) angeboten.
Stellung im Studienplan
BSc Computerlinguistik: | Pflicht |
BA Language Science: | WP 2 Basismodul A (Wahlpflicht) |