• Syllabus

Print View

1. VorlesungFri Apr 25, 2025 12:15 PM -  | 01:45 PM

  • Fleißige Biber
  • LOOP-berechenbare Funktionen
  • nicht (LOOP-) berechenbare Funktionen

2. VorlesungFri May 02, 2025 12:15 PM -  | 01:45 PM

  • primitiv-rekursive Funktionen
  • Primzahlkodierung (Gödelnummern)
  • LOOP-berechenbare Funktionen sind primitiv-rekursiv

3. VorlesungFri May 09, 2025 12:15 PM -  | 01:45 PM

  • primitiv-rekursive Funktionen sind LOOP-berechenbar
  • WHILE und GOTO
  • Registermaschinen (Zählerautomaten)
    • endliche Anzahl an Registern mit unendlichem Wertebereich
    • Gegensatz: Turingmaschinen mit unendlichem Band und endlichem Alphabet
  • Registermaschinen mit 2 Registern (Zählerautomaten) können Turingmaschinen simulieren

4. VorlesungFri May 16, 2025 11:45 AM -  | 01:15 PM

  • Zählerautomaten mit 1 Zähler: Entscheidbarkeit des Halteproblems
  • Minimierung (μ-Rekursion)
  • Partielle Funktionen, berechenbare (partielle) Funktionen
  • Algorithmen, die Programme bearbeiten: Editor, Präprozessor, Makros erweitern, Compiler, Analysewerkzeuge
  • Begriffe/Programme verwenden und erwähnen
  • Selbstdruckende Programme (in Python)

5. VorlesungFri May 23, 2025 12:15 PM -  | 01:45 PM

6. VorlesungFri May 30, 2025 12:15 PM -  | 01:45 PM

  • Beweis der Rekursionssatzes für Turingmaschinen
  • Verstecken von Hintereingängen
  • Satz von Rice
  • Kontextfreie Grammatiken

7. VorlesungFri Jun 06, 2025 12:15 PM -  | 01:45 PM

  • Nichtdeterministische Kellerautomaten: Definition
  • Kontextfreie Sprachen und Kellerautomaten

8. VorlesungFri Jun 13, 2025 12:15 PM -  | 01:45 PM

  • Gültige Konfigurationsfolge für Turingmaschinen
  • Entscheidbare und unentscheidbare Probleme für kontextfreie Sprachen
    • Schnitt zweier Sprachen leer?
    • Ist das Komplement leer?
  • Ist das Komplement eines regulären Ausdrucks eines nichtdeterministischen endlichen Automaten (NEA) leer?
  • Lemma: Turingmaschine mit Platzverbrauch s → regulärer Ausdruck der Größe O(s2) für alle Eingaben außer den akzeptierenden Konfigurationsfolgen.

9. Vorlesung - per VideoFri Jun 20, 2025 12:15 PM -  | 01:45 PM

  • deterministische 2-Wege-Kellerautomaten und das Teilwortproblem (Folien)
    Achtung: Der Keller in den Videos und in den Folien ist von links nach rechts als v1v2…vm dargestellt mit vm als oberstem Kellersymbol, im Gegensatz zur sonst verwendeten Konvention.
    • direkte Simulation (Video 13:30 min, mit Smartplayer, MP4-Datei 17 MByte)
      Videoinhalt
      Nachtrag zum Teilwortproblem 0:00
      Überblick 0:56
      deterministischer 2-Wege-Kellerautomat 1:38
       Eingabeband (nur zum Lesen) 1:43
       Zustandsmenge Q 2:53
       Startzustand q0 3:00
       Kelleralphabet Γ 3:06
       Stapelgrundsymbol Z0 3:36
       Eingabealphabet Σ 4:17
       Übergangsfunktion δ 4:49
      Startkonfiguration 6:05
      Beendung 6:20
      akzeptierende Zustandsmenge F 6:51
      unendliche Schleife 7:21
      Lösung des Teilwortproblems 7:30
      Programmzähler 8:40
      Laufzeit 9:14
      exponentielle Laufzeit: Binärzähler 9:30
      Simulation in linearer Zeit 10:06
      direkte Simulation 10:32
      Abbruchbedingung 10:57
      Ausführung eines Schrittes 11:21
      Beendigung nur mit leerem Stapel 12:44
    • gegliederte Simulation, Abkürzung durch Merken (Video 18 min, mit Smartplayer, MP4-Datei 21 MByte)
      Videoinhalt
      gegliederte Simulation 0:00
      Veränderung des Stapels 1:19
      Ergebnis der Simulationsfunktion 2:31
      rekursive Simulationsfunktion 2:56
      Akzeptieren der Eingabe 5:48
      Vergleich mit der direkten Simulation 6:53
      Vorteil 7:31
      Systematische Reihenfolge der Teilprobleme? 8:27
      Merken der Ergebnisse 8:56
      Unendliche Rekursion 10:27
      Unendliche Schleife im Kellerautomaten 11:15
      Statusabfrage zu Beginn 12:44
      Statusänderung am Ende 13:40
      lineare Laufzeit 13:50
      Zählen der Aufrufe 14:31
      Zusammenfassung und Rückblick 16:06
  • Nachtrag: Hintergrund und Entstehung des Algorithmus von Knuth-Morris-Pratt (1977) zur Teilwortsuche (Video 8 min, mit Smartplayer, MP4-Datei 8 MByte)

10. Vorlesung - per VideoFri Jun 27, 2025 12:15 PM -  | 01:45 PM

  • EBNF zur Beschreibung der Syntax von Programmiersprachen  (Folien, Video 8 min, mit Smartplayer, MP4-Datei 11 MByte)
    Videoinhalt
    Syntax von Programmiersprachen 0:00
    erweiterte Backus-Naur-Form (EBNF)  0:20
    Syntax von Java 1:23
    Elimination der Erweiterungen 3:20
    Beispiel: Methodenaufruf in Java 3:53
    Metasymbole 6:35
  • kontextfreie Datenformate (Video 6 min, mit Smartplayer, MP4-Datei 11 MByte)
    Videoinhalt
    Anwendungen kontextfreier Grammatiken  0:00
    Syntax von Programmiersprachen 0:13
    kontextfreie Datenformate 0:28
    HTML für Netzseiten 0:39
    Quelltext einer Netzseite 1:04
    XML als strukturiertes Datenformat 2:55
    Beispiel einer XML-Datei 3:21
    Baumstruktur 4:39
    • HTML
    • XML, Beispiel NEA.xml einer XML-Datei
  • eindeutige und mehrdeutige Grammatiken (Video 16 min, mit Smartplayer, MP4-Datei 21 MByte)
    Videoinhalt
    mehrdeutige Grammatiken 0:00
    bedingte Anweisung, "if" 3:02
    nachhängendes "else" 4:21
    Unterscheidung der Variablen 6:35
    if-else in Python 8:11
    Priorität bei arithmetischen Ausdrücken 8:29
    eindeutige und mehrdeutige Grammatik  10:05
    Syntaxanalysealgorithmen 11:42
    inhärent mehrdeutige Sprachen 12:48
    Mehrdeutigkeit im Deutschen 15:25
  • Schnitt einer kontextfreien Sprache mit einer regulären Sprache (Folien)
    • Beweis 1: Kellerautomat, Video 10 min, mit Smartplayer, MP4-Datei 12 MByte)
      Videoinhalt
      Schnitt einer kontextfreien Sprache mit einer regulären Sprache  0:00
      Kellerautomat für L 0:38
      Kellerautomat für die Schnittmenge 1:42
      Zustandsmenge: kartesisches Produkt 2:43
      unveränderte Kelleroperationen 3:02
      Startzustand 3:16
      nichtdeteministischer Kellerautomat 3:51
      Übergänge in K 4:25
      Nachfolgezustand 5:05
      Übergänge ohne Eingabesymbol 6:13
      akzeptierende Zustände 7:44
      Rückblick auf die Konstruktion 8:37
      2. Beweis: Tripelkonstruktion 9:16
    • Beweis 2: Tripelkonstruktion, Video 9 min, mit Smartplayer, MP4-Datei 11 MByte)
      Videoinhalt
      Konstruktion ausgehend von Grammatik G  0:00
      Grammatik in Chomsky-Normalform 0:33
      Tripelkonstruktion 1:00
      Regeln 1:20
      Behandlung von Paarregeln 1:23
      Grundidee 2:11
      Zusammenpassen wie Dominosteine 3:22
      Behandlung von Terminalregeln 4:27
      Anfangsregeln 5:47
      Regel für das leere Wort 7:51
  • deterministische kontextfreie Sprachen (Folien, Video 17 min, mit Smartplayer, MP4-Datei 21 MByte)
    Videoinhalt
    deterministischer Kellerautomat 0:00
    deterministische kontextfreie Sprachen 2:18
    Beispiel { 0n1n } 2:48
    Beispiel Dycksprache 3:37
    Palindrome mit markierter Mitte 4:17
    Palindrome ohne Mittelmarkierung 5:02
    Definition mit Akzeptieren durch leeren Keller 5:45
    Mit leerem Keller muss der Automat abbrechen 6:20
    präfixfreie Sprachen 7:46
    Beispiel { 0n1n } + { 0n12n } 8:27
    Beweisidee 9:02
    nicht abgeschlossen unter Umkehrung 10:17
    eindeutige Grammatik 11:19
    keine Umkehrung 12:22
    inhärent mehrdeutige Sprachen 13:14
    Anwendung auf Programmiersprachen 13:38
    Werkzeuge: bison (yacc), und flex 14:54
    • deterministische Kellerautomaten
    • Zusammenhang zu eindeutigen Grammatiken
    • spezielle kontextfreie Grammatiken für Programmiersprachen
    • Werkzeuge: bison (yacc) in Zusammenarbeit mit flex

11. VorlesungFri Jul 04, 2025 12:15 PM -  | 01:45 PM

  • Chomsky-Normalform (CNF) für kontextfreie Sprachen (Folien, Video 27 min, mit Smartplayer, MP4-Datei 34 MByte)
  • [Weglassen: Jede kontextfreie Sprache ist auch kontextsensitiv.]
  • Transformation der Grammatik in CNF
    • Schritt 1: Trennung von Variablen und Terminalsymbolen
    • Schritt 2: Elimination zu langer Regeln
    • Schritt 3: Elimination der ε-Regeln
    • Schritt 4: Elimination der Einheitsregeln (Video 10 min, mit Smartplayer, MP4-Datei 12 MByte)
  • Beispiel 1 (Video 13 min, mit Smartplayer, MP4-Datei 16 MByte)
  • Beispiel 2: eindeutige Grammatik für arithmetische Ausdrücke (Video 12 min, mit Smartplayer, MP4-Datei 14 MByte)

12. VorlesungFri Jul 11, 2025 12:15 PM -  | 01:45 PM

  • PSPACE und NPSPACE
  • L(A)=Σ*? für einen nichtdeterministischen endlichen Automaten A ist PSPACE-vollständig.

13. VorlesungFri Jul 18, 2025 12:15 PM -  | 01:45 PM

  • L(r)=Σ*? für einen regulären Ausdruck r ist PSPACE-vollständig.
    • Abschluss des Beweises
  • L(A)=Σ*? für einen nichtdeterministischen endlichen Automaten A über einem einbuchstabigen Alphabet ist NP-schwer.