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)