• Organisatorisches
• Einführung: Geschichte der Theoretischen Informatik in der Mathematik

[Video aus dem SoSe 2020]

• Einführung: Geschichte der Theoretischen Informatik in der Linguistik
• Einführung: Geschichte der Theoretischen Informatik in der Biologie

• Algorithmische Probleme, Sprachen und das Wortproblem

[Video aus dem SoSe 2020] [Video aus dem SoSe 2020]

• Operationen auf Sprachen
• Reguläre Ausdrücke

[Video aus dem SoSe 2020] [Video aus dem SoSe 2020]

• Deterministische Endliche Automaten - Beispiel
• Deterministische Endliche Automaten - Definition

[Video aus dem SoSe 2020] [Video aus dem SoSe 2020]

• Programmieren mit Deterministischen Endlichen Automaten
• Nichtdeterministische Endliche Automaten - Motivation und Definition

[Video aus dem SoSe 2020] [Video aus dem SoSe 2020] [Video aus dem SoSe 2020]

• Nichtdeterministische Endliche Automaten - Potenzmengenkonstruktion

[Video aus dem SoSe 2020]

• Potenzmengenkonstruktion - Korrektheitsbeweis
• rA -> NEA

[Video aus dem SoSe 2020] [Video aus dem SoSe 2020] [Video aus dem SoSe 2020]

• DEA -> rA (Algorithmus von Kleene)
• Pumping-Lemma - Einführung

[Video aus dem SoSe 2020] [Video aus dem SoSe 2020] [Video aus dem SoSe 2020]

• Pumping-Lemma - Beweis
• Pumping-Lemma - Anwendungen

[Video aus dem SoSe 2020] [Video aus dem SoSe 2020] [Video aus dem SoSe 2020]

• Nerode-Relation
• Minimalautomat - Äquivalenzklassenautomat

[Video aus dem SoSe 2020] [Video aus dem SoSe 2020]

• Minimalautomat - Tabellenausfüllalgorithmus
• Turing-Maschinen - Motivation, Definition und Beispiel

[Video aus dem SoSe 2020] [Video aus dem SoSe 2020]

• Turing-Maschinen - Zweites Beispiel
• Turing-Maschinen - Varianten
• Semientscheidbarkeit und Entscheidbarkeit, Church-Turing These

[Video aus dem SoSe 2020] [Video aus dem SoSe 2020] [Video aus dem SoSe 2020]

• Es gibt nicht semientscheidbare Sprachen - Kardinalitätsargument
• Es gibt nicht semientscheidbare Sprachen - Diagonalsprache
• Es gibt semientscheidbare Sprachen, die nicht entscheidbar sind - Universalsprache

[Video aus dem SoSe 2020] [Video aus dem SoSe 2020] [Video aus dem SoSe 2020]

• Das Halteproblem
• Reduktionen
• Eigenschaften von Reduktionen

[Video aus dem SoSe 2020] [Video aus dem SoSe 2020] [Video aus dem SoSe 2020]

• Abschlusseigenschaften von entscheidbaren und semientscheidbaren Sprachen
• Beispiele für semientscheidbare Sprachen

[Video aus dem SoSe 2020] [Video aus dem SoSe 2020] [Video aus dem SoSe 2020] [Video aus dem SoSe 2020]

• Grammatiken - Definition und Beispiele
• Chomsky-Hierarchie für Grammatiken
• Chomsky-Hierarchie für Sprachen

[Video aus dem SoSe 2020] [Video aus dem SoSe 2020] [Video aus dem SoSe 2020] [Video aus dem SoSe 2020]

• Die Landschaft der Sprachen 
• kontextfreie Grammatiken und Syntaxbäume
• Chomsky-Hierarchie für Sprachen

[Video aus dem SoSe 2020] [Video aus dem SoSe 2020] [Video aus dem SoSe 2020]

• Die Chomsky- Normalform
• Der CYK-Algorithmus

 [Video aus dem SoSe 2020] [Video aus dem SoSe 2020] [Video aus dem SoSe 2020] [Video aus dem SoSe 2020]

• Der CYK-Algorithmus - Beispiel
• Pumping-Lemma für kontextfreie Sprachen - Formulierung und Beispiele
• Pumping-Lemma für kontextfreie Sprachen - Beweis

 [Video aus dem SoSe 2020]  [Video aus dem SoSe 2020] [Video aus dem SoSe 2020]

• Pumping-Lemma für kontextfreie Sprachen - weiteres Beispiel
• Abschlusseigenschaften kontextfreier Sprachen
• Kellerautomaten

 [Video aus dem SoSe 2020]  [Video aus dem SoSe 2020] [Video aus dem SoSe 2020]