CYKAlgorithmus
Der CYK-Algorithmus, auch Cocke–Younger–Kasami-Algorithmus genannt, ist ein Parsing-Verfahren für kontextfreie Grammatiken in Chomskys Normalform. Er entscheidet, ob ein gegebener String von einer CFG erzeugt wird, und kann auf Wunsch eine Parse-Struktur liefern. Die Grammatik muss in CNF vorliegen, d. h. alle Regeln haben die Formen A → BC oder A → a (mit gegebenen Terminalsymbolen) oder, in einigen Fassungen, S → ε für den leeren String.
Der Ablauf basiert auf dynamischer Programmierung. Gegeben sei ein Eingabewort w der Länge n. Es wird eine
Die Komplexität beträgt in CNF-Form O(n^3) Zeit und O(n^2) Speicher. Der Algorithmus ist korrekt und vollständig