• Syllabus

Print View

1. VorlesungMon Oct 20, 2025 10:15 AM -  | 11:45 AM

  • 1. Alphabet, Wörter und Sprachen
    • Operationen auf Sprachen
    • Wortproblem als Abstraktion beliebiger Entscheidungsprobleme
  • 2. reguläre Ausdrücke

2. VorlesungMon Oct 27, 2025 10:15 AM -  | 11:45 AM

  • 3. deterministische endliche Automaten (DEA)
    • erweiterte Übergangsfunktion δ*
  • 4. nichtdeterministische endliche Automaten (NEA)
    • gültige Zustandsfolge für ein Eingabewort; gültige akzeptierende Zustandsfolge
    • Ungleiche Behandlung von akzeptierenden und nicht akzeptierenden Zustandsfolgen
    • Interpretationen des Nichtdeterminismus
      • glückliches Raten
      • gleichzeitiges Abarbeiten aller möglichen gültigen Zustandsfolgen
      • NEAs als Mechanismus zum Erzeugen einer Sprache

3. VorlesungMon Nov 03, 2025 10:15 AM -  | 11:45 AM

  • Prinzipielle Äquivalenz zwischen regulären Ausdrücken, NEAs und DEAs
  • Abschluss gegenüber Komplement
  • Simulation eines NEA mit Menge A der möglichen Zustände, mit Python-Implementierung
  • Umwandlung NEA → DEA: Potenzmengenkonstruktion
  • Abschluss von NEA-Sprachen bezüglich Vereinigung und Konkatenation
NEA.py

4. VorlesungMon Nov 10, 2025 10:15 AM -  | 11:45 AM

  • Abschluss von NEA-Sprachen bezüglich *-Operation
  • Konstruktion eines NEA zu einem regulären Ausdruck
  • Konstruktion einen regulären Ausdrucks für einen endlichen Automaten: Der Algorithmus von Kleene
  • Formulierung des Pumping-Lemmas

5. VorlesungMon Nov 17, 2025 10:15 AM -  | 11:45 AM

  • Abschlusseigenschaften der regulären Sprachen (Zusammenfassung)
  • Das Pumping-Lemma. Beweis und Anwendungsbeispiele
  • Existenz nichtregulärer Sprachen durch ein nicht konstruktives Abzählargument

6. VorlesungMon Nov 24, 2025 10:15 AM -  | 11:45 AM

  • Der Minimalautomat
    • Konstruktion mit dem Tabellenausfüllalgorithmus
    • Trennwörter

7. VorlesungMon Dec 01, 2025 10:15 AM -  | 11:45 AM

  • Der Minimalautomat
    • Minimalität und Eindeutigkeit
  • Turing-Maschinen

8. VorlesungMon Dec 08, 2025 10:15 AM -  | 11:45 AM

  • Varianten von Turing-Maschinen
  • Entscheidbarkeit, Semientscheidbarkeit, Berechenbarkeit
  • Die Church-Turingsche These
  • Kodierung von Turingmaschinen
  • Universelle Turingmaschinen
  • Unentscheidbare Sprachen
    • die Diagonalsprache D

9. VorlesungMon Dec 15, 2025 10:15 AM -  | 11:45 AM

  • Unentscheidbare Sprachen
    • die Unversalsprache U
    • das Halteproblem H
  • Reduktionen zwischen Problemen

10. VorlesungMon Jan 05, 2026 10:15 AM -  | 11:45 AM

  • Abschlusseigenschaften entscheidbarer und semientscheidbarer Sprachen
  • Einige unentscheidbare Sprachen:
    • Postsches Korrespondenzproblem
    • Sterblichkeit von Matrizen
    • Diophantische Gleichungen (Das 10. Hilbertsche Problem)
    • Das Hilbertsche Entscheidungsproblem
  • Polynomielle Laufzeit, die Klasse P
  • Die Klasse NP, polynomielles Zertifikatskriterium
  • polynomielle Reduktion

Vorlesung - 13Mon Jan 12, 2026 10:15 AM -  | 11:45 AM

Vorlesung - 14Mon Jan 19, 2026 10:15 AM -  | 11:45 AM

Vorlesung - 15Mon Jan 26, 2026 10:15 AM -  | 11:45 AM

ProbeklausurMon Feb 02, 2026 10:15 AM -  | 11:45 AM

Vorlesung - 17Mon Feb 09, 2026 10:15 AM -  | 11:45 AM