Formale Sprachen und Automaten
Vorlesung mit Proseminar
CIS, WS 2005/06
Hans Leiß
Vorlesung
Zeit und Raum: Mo 14-16, Oe67, Hörsaal 1.27, und Mi 14-16, Oe67, Hörsaal 0.05
Der Kurs stellt die Theorie der formalen Sprachen und ihrer maschinellen
Analyse vor. Damit werden die Grundlagen für eine Beschäftigung
mit maschineller Analyse natürlicher Sprachen gelegt.
Behandelt werden:
- Reguläre Ausdrücke, als Sprachdefinitionen und als iterative Programme,
- Erkennung regulärer Sprachen durch endliche Automaten,
- Kontextfreie Grammatiken, als Sprachdefinitionen und als rekursive Programme
- Wortstellung, Wiederholungs- und andere Struktureigenschaften
kontextfreier Sprachen,
- Erkennung kontextfreier Sprachen durch Kellerautomaten,
- Bäume als syntaktische Strukturen,
- Grundprinzipien der maschinellen Syntaxanalyse bei kontextfreien
Grammatiken,
- Chomskys Hierarchie formaler Sprachklassen.
Literaturhinweise:
- B.PARTEE/ A.ter MEULEN/ R.E.WALL
-
Mathematical Methods in Linguistics, Chap. 16 - 19, pp. 433 - 506.
Reidel, 1988
- N.MOLL/ M.ARBIB/ A.J.KFOURY
-
An Introduction to Formal Language Theory. Springer-Verlag, 1988
- H.LEISS
- Formale Sprachen und Automaten, Vorlesung WS
97/98. CIS-Bericht 97-109, 1997
.ps
(.pdf)
Korrigierte bzw. erweiterte Teile des Skriptums (darin enthaltene weitere
Aufgaben zur Übung):
- Grundbegriffe
(Ergänzt: 1.13-1.15 zu Monoiden; 6.11.05: Diagonalverfahren, Satz 1.3)
- Reguläre Ausdrücke 1
(Ergänzt: 6.11: 2.4 zu nicht-reg.Sprachen)
Voraussetzungen:
Mathematische Grundlagen I
Übung/Proseminar
Übungsaufgaben werden hier (möglichst) wöchentlich gestellt.
- Sprachprodukt und Monoide
- Monoid-Homomorphismen und Sprachdivision Abgabe Mo 7.11.05
- Relationen-
und Sprachinterpretation regulärer Ausdrücke Abgabe verlängert bis Mo 21.11.05
- Reguläre Sprachen und Programme Abgabe Mo 28.11.05
- Kleene-Algebra, nichtdet.Automaten Abgabe Mo 12.12.05 (auf Mi verlängert für die,
die am Ausgabetermin nicht da waren)
- Det.Automaten
und Sprachquotienten Abgabe Mi 21.12.05
Musterlösung
von Aufgabe 6
- Automaten und Gleichungssysteme Abgabe Mi 18.1.06
Musterlösung
von Aufgabe 7
- Zustandsminimale Automaten Abgabe Mi 25.1.06
-
Grammatiken
und ihre Interpretation durch Fixpunkte Abgabe Mi 1.2.06
File translated from
TEX
by
TTH,
version 3.70.
On 26 Jan 2006, 11:16.