Kursüberblick

(https://www.coli.uni-saarland.de/~saurer/lehre/mg2/mg2-ku.html)

Mathematische Grundlagen der Computerlinguistik II:

Formale Sprachen und Automaten

Sommersemester

Werner Saurer, Tel. 302-4177, Geb. 17.2, Zi.1.08, Sprechstunde: Mi 14-15 Uhr
Stefan Thater, Tel. 302-4496, Geb. 17.2, Zi. 1.11, Sprechstunde: Mi 14-15 Uhr

Lehrbücher:

Partee/ter Meulen/Wall, Mathematical Methods in Linguistics. Kluwer, 1990.
Lewis/Papadimitriou , Elements of the Theory of Computation. Prentice-Hall Int., 1981.

Diese Bücher sind in einem Apparat in der Institutsbibliothek zusammengestellt. Sie können übers Wochenende ausgeliehen werden.

Übungsaufgaben:

Wir werden regelmässig Übungsaufgaben aufgeben, die auch von den Studenten gemacht werden sollten, die keinen Schein wollen. Wir werden in den Übungen auch über diese Aufgaben sprechen. Daneben soll jede/r so viele Aufgaben für sich machen, wie sie/er zeitmässig bewältigen kann. Wir stehen für Fragen immer zur Verfügung.

Klausuren und Noten:

Für diejenigen, die einen Schein wollen, gibt es insgesamt zwei (2) Klausuren ( schriftliche Prüfungen), die rechtzeitig angekündigt werden. Die zwei Klausuren sind jeweils 45 Minuten lang mit jeweils 75 Punkten (+ 6 Punkte für Bonusaufgaben). Die 1. Klausur ist ungefähr in der Mitte des Semesters und deckt den Stoff des 1. Halbsemesters ab. Die 2. Klausur ist kurz vor Semesterende und deckt den Stoff des 2.Halbsemesters ab. Eine nicht geschriebene Klausur zählt 0 Punkte.

Die Note für den benoteten Schein kommt folgendermassen zustande. Nach der 2. Klausur werden die Punkte der beiden Klausuren für eine vorläufige Note zusammengezählt. Dabei entsprechen ungefähr

Punkte Note
>= 135 sehr gut (1)
120-134 gut (2)
105-119 befriedigend (3)
90-104 ausreichend (4)
< 90 nicht bestanden.



Zeitplan (annähernd)

1.-5.Woche


 Reguläre Ausdrücke und reguläre Sprachen; Endliche Automaten - deterministische und nicht-deterministische; Äquivalenz von det. und nicht-det. endl. Automaten; Äquivalenz von endlichen Automaten und regulären Sprachen; Pumping Lemma für reguläre Sprachen; det. endliche Transducer
6.-9.Woche

 Kontextfreie Grammatiken und kontextfreie Sprachen, Pumping Lemma für kontextfreie Sprachen; kontextfreie Sprachen und Kellerautomaten; Parsing: Top-down und Bottom-up Verfahren; det. Kellerautomaten
10.-12.Woche

 Chomsky-Hierarchie, Typ-0-Sprachen; Turingmaschinen; die Universal-Turingmaschine; das Halteproblem für Turingmaschinen; Typ-0-Grammatiken und Turingmaschinen
8.Woche 1.Klausur; Stoff der 1. Hälfte
13.Woche 2.Klausur; Stoff der 2. Hälfte