Lexikon der Mathematik: Cocke-Kasami-Younger-Algorithmus
CYK-Algorithmus, tabellenorientiertes Analyseverfahren für kontextfreie Sprachen.
Vorausgesetzt wird dabei eine kontextfreie Grammatik in Chomsky-Normalform.
Die Idee kann man wie folgt beschreiben: Im ersten Schritt werden im gegebenen Wort alle Terminalsymbole durch Rückwärtsanwendung von Regeln durch Nichtterminalzeichen ersetzt. Gibt es mehrere Möglichkeiten, werden alle Varianten notiert. Danach werden stufenweise Paare benachbarter Nichtterminalzeichen durch Rückwärtsanwendung von Regeln zu einem einzelnen Nichtterminal reduziert. Notiert man die entstehenden Nichtterminalzeichen in der Lücke zwischen den Ausgangszeichen, ensteht eine Dreiecksstruktur, die man auch als obere Dreiecksmatrix anordnen kann.
Der Algorithmus arbeitet für eindeutige kontextfreie Sprachen in einer Laufzeit von O(n2 log n) und für allgemeine kontextfreie Sprachen in O(n3), wobei n die Länge des eingegebenen Wortes ist.
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.