Theoretische Grundlagen der Informatik, Vorlesung, WS15/16

07: Vorlesung und Übung | 0:00:00 Starten 0:00:07 1.3 Kontextfreie Sprachen 0:01:15 Chomsky Hierarchie 0:02:06 Überblick 0:03:39 1.3.1 Normalformen 0:04:46 Epsilon-Eliminiation 0:05:27 Epsilon eliminieren 0:13:38 Beispiel 0:18:25 Korrektheitsbeweis (Skizzenskizze) 0:21:09 Korrektheitsbeweis - Terminierung 0:24:03 Eliminiation von zyklischen Einheitsproduktionen 0:27:12 Eliminiation von nichtzyklischen Einheitsproduktionen 0:30:16 Chomsky Normalform 0:31:53 Eliminiation gemischter rechter

06: Vorlesung | 0:00:00 Starten 0:00:07 Satz von Nerode 0:07:43 Gegenbeispiel NFA 0:08:33 Konstruktion eines zustandsminimalen Automaten 0:09:08 Vorverarbeitung - Beispiel 0:09:42 Äquivalente Zustände 0:10:57 Entfernen äquivalenter Zustände 0:12:10 Zustandsminimierung 0:13:50 Nichtäquivalenz von Zuständen 0:17:45 Kürzeste Zeugen für Nichtäquivalenz 0:23:45 Beispiel 0:26:24 Ein Einfacher Algorithmus 0:32:08 Zustandsminderung in Zeit 0:33:05 Wieso Zustandsminderung 0:34:34 Zustandsminderung in

05: Vorlesung und Übung | 0:00:00 Starten 0:00:08 Wiederholung: DFA - RegExp 0:02:19 Zur Erinnerung: Äquivalenzrelationen 0:05:18 Verfeinerung 0:08:02 Nerode Relation 0:11:01 DEAs induzieren Äquivalenzrelationen 0:14:08 Unendlicher Index der Neroderelation 0:17:55 Äquivalenzklassenautomat 0:35:26 Nerode Relation 0:37:05 Beispiel 0:39:44 Satz von Nerode 0:42:05 2. Übung 0:42:52 Pumping-Lemma 0:46:57 Pumping-Lemma: Beispiel 0:50:41 Epsilon-Abschluss 1:00:02 Nerode-Relation

04: Vorlesung | 0:00:00 Starten 0:00:07 Wiederholung: Reguläre Ausdrücke 0:01:46 Satz: Reguläre Ausdrücke - Typ-3 Sprachen 0:02:25 Regulärer Ausdruck - NFA 0:02:53 RegExp - NFA 0:08:05 Beweis 0:19:15 Positive Hülle 0:20:17 Beweis 0:26:38 Kleensche Hülle 0:27:29 Beispiele 0:32:52 Exkurs: Anwendung Texte durchsuchen 0:37:34 Anwendung Scanner-(Generatoren) 0:40:16 Ähnliche Funktionaliät 0:41:39 Exkurs: Übergänge 0:43:02 NFA 0:43:39 Beispiel 0:44:56 RegExp - NEA 0:45:58 Positive Hülle 0:46:23

03: Vorlesung und Übung | 0:00:00 Starten 0:00:16 Wiederholung: Nichtdeterministische endliche Automaten NFA 0:01:36 NFA - DFA 0:03:18 Potenzmengenkonstruktion 0:03:44 Beispiel 0:10:54 Implementierungshinweise 0:12:42 Typ-3 - NFA 0:16:17 Mehrdeutigkeit bei Typ-3 0:18:21 Reguläre Ausdrücke 0:24:53 Beispiele 0:30:34 Satz: Reguläre Ausdrücke - Typ-3 Sprachen 0:31:54 Regulärer Ausdruck - NFA 0:32:27 Basisfälle 0:33:13 RegExp - NFA 0:36:31 Beweis 0:41:54 1. Übung - TGI 0:42:23 Organisatorisches 0:43:52

02 : Vorlesung und Übung | 0:00:00 Starten 0:00:11 Wdh. Grammatiken 0:01:21 Wdh. Übergangsrelation 0:03:09 Chomsky-Hierarchie 0:13:20 Beweis, Ansatz 0:13:46 Beweis, ausführlich 0:48:06 Beweisskizze 0:51:15 Einschub: lexikographische Reihenfolge 0:53:25 Lemma S 0:56:00 Beweisskizze 1:00:12 Todo 1:00:28 Wortproblem 1:05:39 Laufzeitabschätzung 1:07:12 Syntaxbäume

01 | 0:00:00 Starten0:00:10 Begrüßung 0:01:02 Organisatorisches 0:02:42 Materialien 0:09:46 Einordnung 0:10:52 Einführung 0:19:06 Formale Sprachen - Notation 0:33:00 Typische Fragestellungen 0:35:47 Warum formale Sprachen? 0:43:10 Automatentheorie 0:47:47 Mächtigere Sprachen und Maschinen 0:49:48 Noch mächtigere Maschinen 0:53:23 Komplexitätstheorie 0:58:27 Informationstheorie 1:00:36 Organisatorisches – Theoretische Grundlagen der Informatik 1:00:58 Organisatorisches – Übungsblätter 1:07:24