Werkzeugkasten Automatentheorie #07 - CF-Grammatik in Chomsky-Normalform (CNF) umwandeln (Update)

Der Werkzeugkasten Automatentheorie stellt einfache Vorgehensweisen für Standardprobleme der Theoretischen Informatik vor. Alle Verfahren werden am Beispiel erklärt. Teil 7 befasst sicht mit der Umwandlung einer kontextfreien Grammatik in die Chomsky-Normalform. Wir folgen dabei einem Prozess mit fünf Schritten, um alle Anforderungen der CNF zu erfüllen. Update: Die fehlende Produktion S→a wurde ergänzt. 00:00 Intro 03:05 Schritt 1 Epsilon-Regeln entfernen 06:39 Schritt 2 Regeln mit einer Variablen entfernen 08:30 Schritt 3 Mischungen aus Variablen und Terminalen entfernen 10:29 Schritt 4 Mehrere Terminale entfernen 11:25 Schritt 5 Mehr als zwei Variablen entfernen Die Videoreihe eignet sich zur Wiederholung meiner Vorlesungen in Theoretischer Informatik und verzichtet auf Formalia und Beweise. Hierzu sei auf die Vorlesung selbst und die Sekundärliteratur verwiesen (H.-P. Gumm/M. Sommer: Informatik 3 sowie U. Schöning: Theoretische Informatik - kurzgefasst). Florian Volk Web: digitalvolk.de Twitter/Instagram: @digitalvolk