Cocke-Younger-Kasami-Algorithmus

Der Cocke-Younger-Kasami-Algorithmus (CYK-Algorithmus) ist ein Algorithmus, der das Wortproblem für gegebene kontextfreie Sprachen effizient löst. Die Sprache muss dazu in Form einer Grammatik in Chomsky-Normalform vorliegen.

Inhaltsverzeichnis

1 Idee 2 Algorithmus 3 Komplexität

Idee

Der CYK-Algorithmus ist ein Beispiel für Dynamische Programmierung. Anstatt sofort zu berechnen, ob sich das Wort w der Länge m aus dem Startsymbol ableiten lässt, wird zuerst ermittelt, aus welchen Variablen sich einstellige Teilworte von w ableiten lassen. Davon ausgehend wird für alle zweistelligen Teilworte berechnet, aus welchen Variablen sie sich ableiten lassen. In jedem weiteren Schritt berechnet man jeweils für alle n-stelligen Teilworte, aus welchen Variablen sie sich ableiten lassen. Dies führt man solange fort, bis man alle Variablen aus denen sich w (entspricht dem m-stelligen Teilwort) ableiten lässt, erhält. Das Wort w gehört genau dann zur durch G erzeugten Sprache, wenn sich das Startsymbol unter diesen Variablen befindet.

Algorithmus

Sei die Menge der Variablen, die in der Ableitung vorkommen. .

Gegeben:	Ein Wort ww der Länge nn mit
Eine Grammatik mit GG in Chomsky-Normalform.
Frage:	Ist ?

Wenn ein Wort ww mit und eine kontext-freie Grammatik GG in Chomsky-Normalform gegeben sind, so bestimmt der Algorithmus für jedes , jedes und jede Variable , ob sich das (Teil-) Wort aus AA ableiten läßt; d.h., ob gilt. Dabei ist das (Teil-) Wort ww, das an der Stelle ii beginnt und die Länge jj hat.

Für j = 1j=1 gilt:
Für gilt:

Komplexität

Der Algorithmus entscheidet in , ob ein Wort der Länge nn in der in Chomsky-Normalform gegebenen Sprache LL liegt.

Help build the largest human-edited directory on the web.

Submit a Site - Open Directory Project - Become an Editor