SS 2014: Automaten und Formale Sprachen - Folien und Übungsblätter

Folien

Folien von einzelnen Vorlesungen

  • Vorlesung 1: Organisatorisches, Einleitung, mathematische Grundlagen — Folien, Notizen
  • Vorlesung 2: Grundlagen und mathematische Beweise (Fortsetzung) — Folien, Notizen
  • Vorlesung 3: Mathematische Beweise (Fortsetzung), Sprachen und Grammatiken, das Wortproblem für Typ-1-Sprachen — Folien, Notizen
  • Vorlesung 4: Deterministische endliche Automaten, Konstruktion DFA zur regulären Grammatik, nicht-deterministische endliche Automaten — Folien, Notizen
  • Vorlesung 5: Nichtdeterministische endliche Automaten (Fortsetzung), Potenzmengenkonstruktion, reguläre Ausdrücke (Anfang) — Folien, Notizen
  • Vorlesung 6: Reguläre Ausdrücke, Pumping Lemma (Anfang) — Folien, Notizen
  • Vorlesung 7: Pumping Lemma, Erkennungsäquivalenz und Minimalautomaten — Folien, Notizen
  • Vorlesung 8: Minimalautomaten und Myhill-Nerode-Äquivalenz, Abschlusseigenschaften — Folien, Notizen
  • Vorlesung 9: Algorithmen, Grail-Demo: Wechselseitiger Ausschluss, Kontextfreie Grammatiken — Folien, Notizen, Demo-Quellcode, Grail 2.5 vorkompiliert für Windows, Linux (RPM)
  • Vorlesung 10: Syntaxbäume und Ambiguität, Chomsky-Normalform, CYK-Algorithmus (Anfang) — Folien, Notizen
  • Vorlesung 11: CYK-Algorithmus, Pumping-Lemma für kontextfreie Sprachen — Folien, Notizen
  • Vorlesung 12: Kellerautomaten — Folien, Notizen
  • Vorlesung 13: Umwandlung Kellerautomat -> kontextfreie Gammatik, Abschlusseigenschaften und Algorithmen — Folien, Notizen
  • Vorlesung 14: Deterministische Kellerautomaten, ANTLR-Demo — Folien, Notizen, Demo-Quellcode

Alle Folien

Folien, Notizen

English translation

All slides, All notes (Last updated: 16 July, Lecture 14)

Übungsblätter

© Universität Duisburg-Essen, Lehrstuhl Theoretische InformatikLogin