Formale Sprachen und Automaten
              
Vorlesung mit Übung
CIS, WS 2015/16

Hans Leiß

Vorlesung

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 und endliche Automaten,
  2. Kontextfreie Grammatiken und ihre Normalformen,
  3. Bäume als syntaktische Strukturen,
  4. Erkennung kontextfreier Sprachen durch Kellerautomaten,
  5. Syntaxanalyse bzgl. kontextfreier Grammatiken,
  6. Chomskys Hierarchie formaler Sprachklassen,
  7. Un/Entscheidbare Probleme zu Grammatiken und formalen Sprachen.
Vorlesungsfolien:

Tafelübung

Übungsaufgaben werden hier wöchentlich gestellt und müssen(!) zu Hause bearbeitet werden. Wer nicht ernsthaft versucht, die Aufgaben zu lösen, wird den Vorlesungsstoff nicht verstehen.
Abgabe der Lösung: Do 14:15 Uhr, in der Übungsstunde.
Fragen zur Vorlesung und den Aufgaben werden in der Übungsstunde besprochen.
  1. Aufgabenblatt-1.pdf
  2. Aufgabenblatt-2.pdf
  3. Aufgabenblatt-3.pdf
  4. Aufgabenblatt-4.pdf
  5. Aufgabenblatt-5.pdf
  6. Aufgabenblatt-6.pdf
  7. Aufgabenblatt-7.pdf
  8. Aufgabenblatt-8.pdf
  9. Aufgabenblatt-9.pdf
  10. Aufgabenblatt-10.pdf
  11. Aufgabenblatt-11.pdf

Fragestunde

Mentorenstunde Do, 11-12, Oettingenstr.67, Raum C 110
Tutorenstunde: Di 18-20, U127     Tutor: Raphael Höps

Modulprüfung

Oettingenstr.67, U 151 (Übungsstunde der letzen Vorlesungswoche)
Ergebnisse der Klausur im LSF nachlesbar

Zweitprüfung

Freitag, 4.März 2016, 10-12 Uhr (Raum beantragt: 115 Oettingenstr.67)

Literaturhinweise:
B.PARTEE/ A.ter MEULEN/ R.E.WALL
Mathematical Methods in Linguistics, Chap. 16 - 19, pp. 433 - 506. Reidel, 1988
ELAINE RICH
Automata, Computability, and Complexity, Pearson/Prentice Hall 2008
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 (.pdf)
Voraussetzungen: Kurs über Mathematische Grundlagen der CL


File translated from TEX by TTH, version 3.67.
On 2 Feb 2016, 14:21.