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:
  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)
Korrigierte bzw. erweiterte Teile des Skriptums (darin enthaltene weitere Aufgaben zur Übung):
  1. Grundbegriffe (Ergänzt: 1.13-1.15 zu Monoiden; 6.11.05: Diagonalverfahren, Satz 1.3)
  2. 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.
  1. Sprachprodukt und Monoide
  2. Monoid-Homomorphismen und Sprachdivision Abgabe Mo 7.11.05
  3. Relationen- und Sprachinterpretation regulärer Ausdrücke Abgabe verlängert bis Mo 21.11.05
  4. Reguläre Sprachen und Programme Abgabe Mo 28.11.05
  5. Kleene-Algebra, nichtdet.Automaten Abgabe Mo 12.12.05 (auf Mi verlängert für die, die am Ausgabetermin nicht da waren)
  6. Det.Automaten und Sprachquotienten Abgabe Mi 21.12.05
    Musterlösung von Aufgabe 6
  7. Automaten und Gleichungssysteme Abgabe Mi 18.1.06
    Musterlösung von Aufgabe 7
  8. Zustandsminimale Automaten Abgabe Mi 25.1.06
  9. 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.