Informatik

Was macht der CYK-Algorithmus?

Der CYK-Algorithmus entscheidet für eine kontextfreie Grammatik in Chomsky-Normalform, ob ein Wort erzeugt wird.

Er nutzt dynamische Programmierung über Teilwörter. Laufzeit typischerweise O(n3∣G∣)O(n^3|G|).

Tabellenidee

table S A,B C,S a b a

Unten stehen Variablen für einzelne Zeichen; darüber Variablen für längere Teilwörter.