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.

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 $V i j$ die Menge der Variablen, die in der Ableitung $A \Rightarrow^{*} w_{ij}$ vorkommen. $w \in L(G) \Leftrightarrow S \in V_{1n}$ .

Gegeben:	Ein Wort $w$ der Länge $n$ mit $w = a_1 a_2 \dots a_n$
	Eine Grammatik $G = \left( N, \Sigma, P, S \right)$ mit $G$ in Chomsky-Normalform.
Frage:	Ist $w \in L(G)$ ?

Wenn ein Wort $w$ mit $\vert w \vert \geq 1$ und eine kontext-freie Grammatik $G$ in Chomsky-Normalform gegeben sind, so bestimmt der Algorithmus für jedes $i \in \mathbb{N}$ , jedes $j \in \mathbb{N}$ und jede Variable $A \in N$ , ob sich das (Teil-) Wort $w i j$ aus $A$ ableiten läßt; d.h., ob $A \Rightarrow^{*} w_{ij}$ gilt. Dabei ist $w i j$ das (Teil-) Wort $w$ , das an der Stelle $i$ beginnt und die Länge $j$ hat.

Für $j = 1$ gilt:	$A \Rightarrow^{*} w_{ij} \Leftrightarrow A \rightarrow w_{ij} \in P$
Für $j > 1$ gilt:	$A \Rightarrow^{} w_{ij} \Leftrightarrow A \rightarrow BC \in P \mbox{ } \wedge \exists \mbox{ } k (1 \leq k \leq j): B \Rightarrow^{} w_{ik} \wedge C \Rightarrow^{*} w_{i+k,j-k}$

Komplexität

Der Algorithmus entscheidet in $O(n 3)$ , ob ein Wort der Länge $n$ in der in Chomsky-Normalform gegebenen Sprache $L$ liegt.

Cocke-Younger-Kasami-Algorithmus

Idee

Algorithmus

Komplexität

See also: Cocke-Younger-Kasami-Algorithmus, Ableitung (Informatik), Algorithmus, Chomsky-Hierarchie, Chomsky-Normalform, Dynamische Programmierung, Formale Grammatik, Kontextfreie Sprache, Wort (Informatik), Wortproblem