Der CYK-Algorithmus 64

Der CYK-Algorithmus (Cocke, Younger, Kasami) ist eine Möglichkeit das Wortproblem für kontextfreie Sprachen zu lösen. Dafür muss die Grammatik in der Chomsky Normalform vorliegen (gegeben falls umformen).

1. Erstelle eine Tabelle, deren Zeilenanzahl $z$ gleich der Länge des Wortes $w$ ist, für das dass Wortproblem gelöst werden soll. Die Spaltenanzahl $s$ ist um eins höher.
2. Trage in die erste Zeile die einzelnen Terminale von $w$ ein.
3. Trage in die Zweite Spalte alle Variablen ein, aus denen man die Variablen oberhalb von ihnen ableiten kann.
4. Fülle die restlichen Zellen nun zeilenweise aus. Beachte, das man in der $j$ ten Zeile immer nur die ersten $\left\vert w\right\vert-j+1$ Zellen ausfüllen braucht (kann).
   1. in die Aktuelle Zelle $x_{j,i}$ kommen alle Variablen $V$ hinein, aus denen man $AB$ ableiten kann ( $V\rightarrow AB$), wobei $A$ ein Element der Menge aller Zelleninhalte oberhalb $\left(\uparrow\right)$ von $x_{j,i}$ und $B$ ein Element der Menge aller Zelleninhalte diagonal rechts oberhalb $\left(\nearrow\right)$ von $x_{j,i}$ ist.
5. Wenn das Startsymbol $S$ ein Element der ersten Zelle der letzten Zeile ist, dann ist $w\in L\left(G\right)$ ansonsten $w\notin L\left(G\right)$.