Reguläre Sprachen sind eine echte Teilmenge der kontextfreien Sprachen. In diesem Video zeigen wir das, indem wir endliche Automaten in kontextfreie Grammatiken verwandeln. Das es umgekehrt jedoch kontextfreie Sprachen gibt, die nicht regulär sind, zeigen wir an einem einfachen Beispiel.
0:00 Start
2:10 Beispiel kontextfrei aber nicht regulär
6:06 Endliche Automaten als Generatoren
8:31 Unproduktive Zustände
10:28 Beispiel für Umwandlung in CFG
13:05 Allgemein: Umwandlung Automat in CFG
18:41 reguläre Grammatiken
