Formale Grundlagen der Linguistik
Kursbeschreibung
| DozentInnen | Matthias Hartung |
| Veranstaltungsart | Vorlesung/Übung |
| Zeit und Ort | Mi, 16:15 - 17:45, INF 306 / SR 13 (SR) |
| Studiengang | ABA, Magister, NBA |
| Modul-Kürzel | ABA: B05, NBA: FF-FM |
| Leistungsbewertung | ABA: 4 LP NBA: 6 LP |
Teilnahmevoraussetzungen
Keine Voraussetzungen
Leistungsnachweis
Klausur
Inhalt
Die Veranstaltung ist als Einführung in die Theorie formaler Sprachen konzipiert. Das in der Vorlesung zu erwerbende Grundwissen
ist zum Verständnis der formalen Eigenschaften vieler Ansätze der Computerlinguistik zentral. Darunter fallen u.a. Grammatiktheorien
in der formalen Linguistik, modelltheoretische Semantiken sowie Parsingverfahren. Insbesondere werden in der Vorlesung folgende
Themen behandelt:
- Mathematische Grundlagen (Mengen, Funktionen, Relationen)
- Formale Sprachen und Grammatiken
- Reguläre Sprachen und endliche Automaten
- Kontextfreie Sprachen
- Kontextsensitive und Typ-0 Sprachen
- Turing-Maschinen
- Berechenbarkeitstheorie
Kursübersicht
Seminarplan
| Datum | Sitzung | Materialien |
| 21.10. | Einführung; Logische Grundlagen | Folien |
| 28.10. | Mengentheoretische Grundlagen | Folien (Update: 01.02.) |
| 04.11. | Relationen | Folien |
| 11.11. | Funktionen | Folien |
| 18.11. | Formale Sprachen | Folien |
| 25.11. | Grammatiken; Allgemeine Regelgrammatik | Folien |
| 02.12. | Endliche Automaten: Einführung | Folien (Update: 09.12.) |
| 09.12. | Reguläre Sprachen | Folien |
| 16.12. | Nicht-deterministische endliche Automaten | Folien |
| 20.01. | Reguläre Ausdrücke; Pumping Lemma für reguläre Sprachen | Folien (Update: 28.01.) |
| 27.01. | Kontextfreie Sprachen; Ausblick | Folien |
Aufgaben
Literatur
-
Schöning, U.: Theoretische Informatik kurzgefasst, Spektrum, 2001
- Vossen, G. und Witt, K.-U.: Grundlagen der Theoretischen Informatik mit Anwendungen, Vieweg, 2001
- Klabunde, R.: Formale Grundlagen der Linguistik, Narr, 1998
- Partee, B. et al.: Mathematical Methods in Linguistics, Kluwer, 1990
- Hopcroft, J.E. and Ullman, J.D.: Introduction to Automata Theory, Languages and Computation, Addison Wesley, 1979