Werkzeugkasten Automatentheorie #08 - CYK-Algorithmus

Der Werkzeugkasten Automatentheorie stellt einfache Vorgehensweisen für Standardprobleme der Theoretischen Informatik vor. Alle Verfahren werden am Beispiel erklärt.
Teil 8 erklärt den CYK-Algorithmus von Cocke, Younger, Kasami, mit dem man das Wortproblem für Sprachen löst, die als kontextfreie Grammatiken angegeben sind.
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

[@Senauce]

Vielen Dank für das Video. Sehr gut erklärt!

[@muhammedgold3]

Bei S fehlt doch S-> a was du im letzten Video also #07 was du geupdatet hast, verändert sich nicht dadurch der CYK Algorithmus?. EDIT: Habe es nachgerechnet und nein, es verändert sich nichts

[@DailyShit.]

S und Sˋ sind eigentlich eh äquivalent und man kann als Außnahme für die CNF auch Sˋ -> S einsetzen und sich eine Zeile und immer eine Variable sparen.