Formale Sprachen und Automaten
              
Vorlesung mit Übung
CIS, WS 2016/17

Hans Leiß

Vorlesung Di 14-16, B U101, Oettingenstr.67

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. Interpretationen kontextfreier Grammatiken,
  4. Erkennung kontextfreier Sprachen durch rekursive endliche Automaten und Kellerautomaten,
  5. Syntaxanalyse bzgl. kontextfreier Grammatiken,
  6. Chomskys Hierarchie formaler Sprachklassen,
  7. Un/Entscheidbare Probleme zu Grammatiken und formalen Sprachen.
Vorlesungsfolien:

Tafelübung Do 14-16, U151, Oettingenstr.67

Ü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 (Loesungsblatt-1.pdf)
  2. Aufgabenblatt-2.pdf (Loesungsblatt-2.pdf)
  3. Aufgabenblatt-3.pdf (Loesungsblatt-3.pdf)
  4. Aufgabenblatt-4.pdf (Loesungsblatt-4.pdf)
  5. Aufgabenblatt-5.pdf (Loesungsblatt-5.pdf)
  6. Aufgabenblatt-6.pdf (Loesungsblatt-6.pdf)
  7. Aufgabenblatt-7.pdf (Loesungsblatt-7.pdf)
  8. Aufgabenblatt-8.pdf (Loesungsblatt-8.pdf, Fehler: in 8.2 (a) war L = {(ab)2nb(ba)n | n in Nat} gemeint!)
  9. Aufgabenblatt-9.pdf (Loesungsblatt-9.pdf)
  10. Aufgabenblatt-10.pdf (Loesungsblatt-10.pdf)
    Die Lösung zu Aufgabe 10.2 sollte doch stimmen: daß in (iii) beim Automaten für (ab)*a der Zustand 5 ein Anfangszustand ist, kommt daher, daß im epsilon-Automaten für (ab)*a eine epsilon-Kante vom Anfangszustand 0 zum Zustand 5 ging. Das hatten wir in der Übungsstunde vielleicht übersehen.
  11. Aufgabenblatt-11.pdf (Loesungsblatt-11.pdf)
  12. Aufgabenblatt-12.pdf (Loesungsblatt-12.pdf)

Fragestunde

Mentorenstunde Do, 11-12, Oettingenstr.67, Raum C 110
Tutorenstunde: ??     Tutor: Raphael Höps

Modulprüfung

Erstprüfung: Wegen Konflikten mit anderen Klausuren (nach Absprache in der Übungsstunde) verschoben auf: Fr 10.2.2017, 12-14 Uhr, Raum B 001
Zweitprüfung: Do 9.3.2017, 10-12, Raum B 001 (Anmeldemoeglichkeit im LSF unter Modulpruefung, Termin 02, nicht unter Wiederholungspruefung.!)

Korrektureinsicht: Di. 21.03.2017, 16-17 Uhr, Hörsaal 151, 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 Mar 2017, 19:51.