Cocke-Younger-Kasami-Algorithmus

Der Cocke-Younger-Kasami-Algorithmus

Der Algorithmus von Cocke, Younger und Kasami ist ein Algorithmus für kontextfreie Grammatiken und Sprachen. Der Algorihtmus liefert eine Antwort: JA oder NEIN, zu der Frage, ob ein Wort aus einer betrachteten kontextfreien Grammatik entstanden sein kann. Um den Cocke-Younger-Kasami-Algorithmus anwenden zu können, muss die betrachtete Grammatik erstmal auf Chomsky-Normalform gebracht werden, wozu ein Algorithmus angewendet werden kann.

Die Komplexität des CYK-Algorithmus liegt in O(n3).