Formale Sprachen und Automaten
              
Vorlesung mit Proseminar
CIS, WS 2007/08

Hans Leiß

Vorlesung

Zeit und Raum: Di 10-12, Oe67, Hörsaal 1.13, und Do 10-12, Oe67, Hörsaal 1.13

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 iterative Programme,
  2. Erkennung regulärer Sprachen durch endliche Automaten,
  3. Kontextfreie Grammatiken, als Sprachdefinitionen und als rekursive Programme
  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.LEISS
Formale Sprachen und Automaten, Vorlesung WS 97/98. CIS-Bericht 97-109, 1997 .ps (.pdf)
Voraussetzungen:
Mathematische Grundlagen I

Übung/Proseminar

Übungsaufgaben werden hier (möglichst) wöchentlich gestellt.
  1. Abgabe Di 30.10.07 Sprachprodukt und Sprachdivisionen
  2. Abgabe Di 06.11.07 Lexikographische Ordnung, Reguläre Sprachen
  3. Abgabe Di 13.11.07 Reguläre Ausdrücke, Sprach- und Relationeninterpretation
  4. Abgabe Di 20.11.07
  5. Abgabe Di 04.12.07 Nicht/Deterministische endliche Automaten, Matrixdarstellung von Automaten
  6. Abgabe Di 11.12.07 Konstruktion deterministischer endlicher Automaten durch Sprachdivision
  7. Abgabe D0 20.12.07 Lemma von Arden, Halbringe, Kleene-Algebren
  8. Abgabe Di 15.1.08 Von Automaten zu regulären Ausdrücken
  9. Abgabe Di 24.1.08 Zustandsminimierung von Automaten, Äquivalenz regulärer Ausdrücke
Am Ende des Semesters wird eine Abschlußklausur geschrieben.


File translated from TEX by TTH, version 3.67.
On 24 Jan 2008, 18:15.