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

Folien

  • Vorlesung 1 – Organisatorisches und Einführung
    1x1, 2x2, Anmerkungen
  • Vorlesung 2 – Grammatiken und die Chomsky-Hierarchie, Wortproblem für Chomsky-1-Sprachen, deterministische endliche Automaten
    1x1, 2x2, Anmerkungen
  • Vorlesung 3 – nichtdeterministische endliche Automaten, reguläre Ausdrücke
    1x1, 2x2, Anmerkungen
  • Vorlesung 4 – reguläre Ausdrücke (Fortsetzung), das Pumping-Lemma
    1x1, 2x2, Anmerkungen
  • Vorlesung 5 – Pumping-Lemma-Beispiel, Myhill-Nerode-Äquivalenz, Minimalautomaten, Abschlusseigenschaften regulärer Sprachen (unter Vereinigung, Konkatenation, Kleene-Stern)
    1x1, 2x2, Anmerkungen
  • Vorlesung 6 – Abschlusseigenschaften regulärer Sprachen (Fortsetzung), Lösungsverfahren, Anwendung: Programmverifikation
    1x1, 2x2, Anmerkungen
  • Vorlesung 7 – Kontextfreie Grammatiken, Eindeutigkeut, Chomsky-Normalform, CYK-Algorithmus
    1x1, 2x2, Anmerkungen
  • Vorlesung 8 – CYK-Algorithmus, Pumping-Lemma für kontextfreie Sprachen
    1x1, 2x2, Anmerkungen
  • Vorlesung 9 – Kellerautomaten
    1x1, 2x2, Anmerkungen
  • Vorlesung 10 – Kellerautomat-Umwandlungen, Abschlusseigenschaften kontextfreier Sprachen
    1x1, 2x2, Anmerkungen
  • Vorlesung 11 – Algorithmen auf kontextfreien Sprachen, deterministische Kellerautomaten, JavaCC
    1x1, 2x2, Anmerkungen, Quellcode

Alle Folien

Alle Folien bis 28.6.2011 – 1x1, 2x2, Anmerkungen

Übungsblätter

  • Übungsblatt 1: [pdf]
    Exercise Sheet 1: [pdf]
    Datum / Date: 12.04.11
    Abgabe / Submission: 19.04.11
  • Übungsblatt 2: [pdf]
    Exercise Sheet 2: [pdf]
    Datum / Date: 19.04.11
    Abgabe / Submission: 26.04.11
  • Übungsblatt 3: [pdf]
    Exercise Sheet 3: [pdf]
    Datum / Date: 26.04.11
    Abgabe / Submission: 03.05.11
  • Übungsblatt 4: [pdf]
    Exercise Sheet 4: [pdf]
    Datum / Date: 03.05.11
    Abgabe / Submission: 10.05.11
  • Übungsblatt 5: [pdf]
    Exercise Sheet 5: [pdf]
    Datum / Date: 10.05.11
    Abgabe / Submission: 17.05.11
  • Übungsblatt 6: [pdf]
    Exercise Sheet 6: [pdf]
    Datum / Date: 17.05.11
    Abgabe / Submission: 24.05.11
  • Übungsblatt 7: [pdf]
    Exercise Sheet 7: [pdf]
    Datum / Date: 24.05.11
    Abgabe / Submission: 31.05.11
  • Übungsblatt 8: [pdf]
    Exercise Sheet 8: [pdf]
    Datum / Date: 31.05.11
    Abgabe / Submission: 07.06.11
  • Übungsblatt 9: [pdf]
    Exercise Sheet 9: [pdf]
    Datum / Date: 07.06.11
    Abgabe / Submission: 15.06.11
  • Übungsblatt 10: [pdf]
    Exercise Sheet 10: [pdf]

    Datum / Date: 21.06.11
    Abgabe / Submission: 28.06.11
  • Übungsblatt 11: [pdf]
    Exercise Sheet 11: [pdf]

    Datum / Date: 28.06.11
    Abgabe / Submission: 05.07.11
© Universität Duisburg-Essen, Lehrstuhl Theoretische InformatikLogin