Cocke-Younger-Kasami-Algorithmus

Der Cocke-Younger-Kasami-Algorithmus (CYK-Algorithmus) ist ein Algorithmus aus dem Gebiet der Theoretischen Informatik. Mit ihm lässt sich feststellen, ob ein Wort zu einer bestimmten kontextfreien Sprache gehört. In der Fachsprache bezeichnet man dies als Lösen des Wortproblems für kontextfreie Sprachen. Um den Algorithmus anzuwenden, muss zu der vorgegebenen Sprache eine Grammatik in Chomsky-Normalform vorliegen.

Der CYK-Algorithmus nutzt das Prinzip der dynamischen Programmierung. Im ersten Schritt ermittelt er, aus welchen Symbolen sich die einstelligen Teilworte (Buchstaben) $a_{i}$ des vorgegebenen Wortes $w=a_{1}\dots a_{n}$ erzeugen lassen. In jedem weiteren Schritt wird dann ermittelt aus welchen Symbolen sich die 2-stelligen, 3-stelligen ... Teilworte erzeugen lassen. Dabei benutzt man die Ergebnisse der vorhergegangenen Schritte. Im letzten Schritt erhält man die Symbole, aus denen sich das n-stellige Teilwort, das dem ursprünglichen Wort entspricht, erzeugen lässt. Wenn sich darunter das Startsymbol befindet, dann lässt sich das vorgegebene Wort $w$ durch die Grammatik erzeugen. Das ist gleichbedeutend damit, dass dieses Wort zur durch die Grammatik repräsentierten Sprache gehört. Andernfalls ist dies nicht möglich.

Beispiel

Die Fragestellung lautet, ob sich das Wort $bbabaa$ durch die Grammatik $G=(\lbrace S,A,B,C\rbrace ,\lbrace a,b\rbrace ,P,S)$ erzeugen lässt. Die Produktionen $P$ der Grammatik seien:

$S\rightarrow AB\mid BC$

$A\rightarrow BA\mid a$

$B\rightarrow CC\mid b$

$C\rightarrow AB\mid a$

Den Algorithmus kann man mittels einer Tabelle durchführen. Dabei steht in der i. Spalte und j. Zeile, aus welchen Symbolen sich das Teilwort $a_{i}\dots a_{j}$ ableiten lässt.

j=6	S,A	S,A	S,A	-	B	A,C
j=5	B	B	B	S,A	A,C
j=4	S,C	S,C	S,C	B
j=3	A	S,A	A,C
j=2	-	B
j=1	B
i	1	2	3	4	5	6
ai	b	b	a	b	a	a

Wenn sich am Ende das Startsymbol in der oberen linken Ecke befindet, lässt sich das gegebene Wort (wie hier) aus S ableiten und damit durch die Grammatik erzeugen.

Algorithmus

Im Folgenden ist$V_{i,j}$ jeweils die Menge aller Variablen aus denen das Teilwort $w_{i,j}$ erzeugt werden kann. Im obigen Beispiel ist beispielsweise $V_{2,3}=\{S,A\}$, da das Teilwort $w_{2,3}=ba$ aus den Symbolen $S$ und $A$ erzeugt werden kann:

$A\to BA\to bA\to ba$

$S\to BC\to bC\to ba$

Als Eingabe erhält der Algorithmus eine kontextfreie Grammatik in Chomsky-Normalform und das zu prüfende Wort.

Im ersten Schritt bestimmt der Algorithmus alle Mengen $V_{i,i}$ der aus einem Buchstaben bestehenden Teilworte. Im Beispiel: $V_{1,1}=\{B\}$, da das Teilwort $w_{1,1}=b$ nur aus dem Symbol $B$ durch die Ableitung $B\to b$ erzeugt werden kann.

Der Algorithmus bestimmt für jedes $i\in \mathbb {N}$, jedes $j\in \mathbb {N}$ und jede Variable $A\in N$, ob sich das (Teil-) Wort $w_{ij}$ aus $A$ ableiten lässt; d.h., ob $A\to ^{*}w_{ij}$ gilt. Dabei ist $w_{ij}$ das (Teil-) Wort von $w$, das die Buchstaben vom Index $i$ bis zum Index $j$ enthält.

Für $j=i$ gilt:$A\to ^{*}w_{ij}\Leftrightarrow A\rightarrow w_{ij}\in P$

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

Komplexität

Der Algorithmus entscheidet, in Landau-Notation ausgedrückt, in ${\mbox{O}}(n^{3})$, ob ein Wort der Länge $n$ in der in Chomsky-Normalform gegebenen Sprache $L$ liegt. Dabei benötigt er Speicherplatz in der Größenordnung ${\mbox{O}}(n^{2})$.

Weblinks

• Interaktives Java-Applet zur Demonstration