24 | 0:00:00 Start 0:00:39 Wiederholung(Turingmaschinen) 0:02:42 Endliche Automaten 0:03:56 Reguläre Ausdrücke 0:07:50 Klammereinsparungsregeln 0:12:41 Durch R Beschriebene formale Sprachen / Beispiel 0:14:49 Beispiele für R 0:27:56 Charakterisierungen regulärer Sprachen 0:34:39 Rechtslineare Grammatiken (Typ 3) 0:39:02 Rechtslineare Grammatiken: Beispiele 0:44:42 Sprechweisen 0:47:29 Vorteile rechtslinearer Grammatiken 0:49:49 Kantorowitsch-Bäume und strukturelle Induktion 0:52:31 Mit Kantorowitsch-Bäumen kann man z.B. reguläre Ausdrücke repräsentieren 0:56:25 Regex-Bäume -- etwas genauer 1:00:06 Vollständige Induktion über die Baumhöhe 1:04:44 Skizze des Induktionsschritts 1:12:15 Zusammenfassung 1:14:29 Äquivalenzrelationen 1:15:48 Kongruenz ganzer Zahlen modulo n 1:16:59 Beispiel: asymtptotisches gleiches Wachstum 1:17:33 Urbilder von Fuktionswerten