Formale Sprachen und Automaten
              
Vorlesung mit Proseminar
CIS, WS 2003/04

Hans Leiß

Vorlesung

Zeit und Raum: Di 16-18, Raum 1.27

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:

1. Reguläre Ausdrücke, als Sprachdefinitionen und als Programme,
2. Erkennung regulärer Sprachen durch endliche Automaten,
3. Definition von Sprachen durch kontextfreie Grammatiken,
4. Wortstellung, Wiederholungs- und andere Struktureigenschaften kontextfreier Sprachen,
5. Erkennung kontextfreier Sprachen durch Kellerautomaten,
6. Bäume als syntaktische Strukturen,
7. Grundprinzipien der maschinellen Syntaxanalyse bei kontextfreien Grammatiken
8. 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.Leiß, Skriptum Atomaten und Formale Sprachen, WS 1997/98

(wird im Laufe des Semesters ggf. verbessert)

Übung

Zeit und Raum: Do 10-12, Raum 0.05

1. Partielle Ordnung, Lexikographische Ordnung
2. Relationen- und Sprachinterpretation regulärer Ausdrücke
3. Nicht-deterministische Endliche Automaten
4. Deterministische endliche Automaten, Teilwortsuche
5. Pumping-Lemma, Epsilon-Automaten, Sprachdivision
6. Lineare Sprachen, Einfügung
7. Fixpunkte und reguläre Gleichungen
8. Bedeutung einer kontextfreien Grammatik auf einem Text; rekursive endliche Automaten