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. Mit Hilfe von Backtracking kann der Parse-Tree bzw. die Parse-Trees eines gegebenen Wortes der Sprache konstruiert werden. Um den Algorithmus anzuwenden, muss zu der vorgegebenen Sprache eine Grammatik in Chomsky-Normalform vorliegen. Der in den 1960er Jahren von Itiroo Sakai, John Cocke, Tadao Kasami, Jacob Schwartz und Daniel Younger unabhängig voneinander entwickelte Algorithmus nutzt das Prinzip der dynamischen Programmierung.

Beschreibung

Diese Beschreibung folgt Hopcroft/Ullman (1996).

Als Eingabe erhält der Algorithmus eine kontextfreie Grammatik G = (N,T,P,S) in Chomsky-Normalform und das zu prüfende Wort $w = w_1w_2\ldots w_n \in T^*$. Nun wird für jedes Teilwort $w_{i,j} := w_i\ldots w_{i+j-1}$ (d.h.: w_i,j fängt beim Index i an und hat die Länge j) die Menge der Nichtterminale berechnet, die w_i,j erzeugen, bezeichnet durch V_i,j.

Gemäß dem Prinzip der dynamischen Programmierung werden erst die V_i,j für die kleinsten Teilwörter von w berechnet, abgespeichert und dann zur somit effizienten Berechnung der nächstgrößeren Teilwörter weiterverwendet. Die kleinsten Teilwörter sind einzelne Buchstaben. Da die kontextfreie Grammatik in Chomsky-Normalform gegeben ist, kann jeder Buchstabe nur in genau einem Schritt von einem Nichtterminal abgeleitet werden.

Ein Nichtterminal einer Grammatik in Chomsky-Normalform kann in einem Schritt nicht auf mehrere Terminale abgeleitet werden. Daher kann ein Teilwort w_i,j, das mehr als nur ein Zeichen enthält, von A nur über eine Regel $(A \rightarrow BC) \in P$ erzeugt werden. Da Nichtterminale nicht das leere Wort (ε) erzeugen können, muss B den linken und C den rechten Teil von w_i,j erzeugen. Daraus folgt:

$A \in V_{i,j} \Leftrightarrow \exists k \in \mathbb{N}, 1 \le k \le j - 1: (A \rightarrow BC) \in P \and B \in V_{i,k} \and C \in V_{i + k, j - k}$

Mit anderen Worten: A kann w_i,j erzeugen, wenn es gemäß der Produktionsregeln auf BC abgeleitet werden kann und B und C wiederum auf w_i,k und w_{i + k,j − k} abgeleitet werden, also $A \rightarrow BC \rightarrow w_i\ldots w_{i+k-1}C \rightarrow w_i\ldots w_{i+k-1}w_{i+k}\ldots w_{i+j-1} = w_{i,j}$.

Das Wortproblem kann nun einfach entschieden werden: w kann genau dann von der Grammatik erzeugt werden, wenn $S\in V_{1,n}$ gilt. In V_1,n liegen alle Variablen, die das Teilwort erzeugen können, das beim ersten Buchstaben anfängt und die Länge n hat, also das ganze Wort.

Algorithmus

Aus der Beschreibung ergibt sich folgender Algorithmus:

Für i = 1 ... n
  Für jede Produktion $(l \rightarrow r) \in P$
    Falls r = wi
      Setze $V_{i,1}:=V_{i,1} \cup \{ l \}$
Für j = 2 ... n
  Für i = 1 ... n - j + 1
    Für k = 1 ... j - 1
      Für jede Produktion $(l \rightarrow BC) \in P$
        Falls $B \in V_{i,k}$ und $C \in V_{i + k, j - k}$
          Setze $V_{i,j}:=V_{i,j} \cup \{ l \}$
Falls $S \in V_{1,n}$, stoppe und gib "w wird von G erzeugt" aus
Stoppe und gib "w wird nicht von G erzeugt" aus

Beispiel

Die Fragestellung lautet, ob sich das Wort w, w = bbabaa durch die Grammatik G = ({S,A,B,C},{a,b},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 ist in der i-ten Zeile und j-ten Spalte V_i,j gespeichert, also die Menge der Nichtterminalsymbole, aus denen sich das Teilwort ableiten lässt, das beim Index i anfängt und die Länge j hat.

Vi,j	1	2	3	4	5	6
1	{B}	{}	{A}	{S,C}	{B}	{A,S}
2	{B}	{S,A}	{S,C}	{B}	{A,S}
3	{A,C}	{S,C}	{B}	{S,A}
4	{B}	{A,S}	{}
5	{A,C}	{B}
6	{A,C}

Da $S\in V_{1,6}$, lässt sich das gegebene Wort w = bbabaa unter der Grammatik G aus S ableiten. Also ist w ein Wort der Sprache L(G).

Komplexität

Der Algorithmus entscheidet in der Zeit $\mathcal{O}(n^3 \cdot \left|P\right|)$, ob ein Wort der Länge n in der Sprache L(G) liegt (vgl. Landau-Symbole zur Beschreibung der Notation). $\left|P\right|$ bezeichnet hier die Größe der Produktionen. Da die Grammatik G in Chomsky-Normalform ist, gilt $\#\mbox{Produktionsregeln} = \Theta(\left|P\right|)$. Mit $p=\#\mbox{Produktionsregeln}$ ergibt sich eine Zeitkomplexität von $\mathcal{O}(n^3 \cdot p)$. Dabei wird Speicherplatz in der Größenordnung $\mathcal{O}(n^2 \cdot \left|P\right|) = \mathcal{O}(n^2 \cdot p)$ benötigt.

Literatur

• Itiroo Sakai: Syntax in universal translation. In: 1961 International Conference on Machine Translation of Languages and Applied Language Analysis. Her Majesty's Stationery Office, London 1962, S. 593–608 (PDF).
• Tadao Kasami: An efficient recognition and syntax-analysis algorithm for context-free languages. Air Force Cambridge Research Lab, Bedford 1965, (Scientific report AFCRL-65-758).
• Daniel H. Younger: Recognition and parsing of context-free languages in time n³. In: Information and Control. 10, Nr. 2, 1967, S. 189–208.
• John Cocke, Jacob T. Schwartz: Programming languages and their compilers. Preliminary notes. Courant Institute of Mathematical Sciences of New York University, New York 1970.
• John E. Hopcroft, Jeffrey D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. 3. Auflage. Addison-Wesley, Bonn 1996, S. 148–149.
• Dick Grune, Ceriel J. H. Jacobs: Parsing Techniques. A Practical Guide. 1. Auflage. Ellis Horwood, New York 1990, ISBN 0-13-651431-6, S. 81–104 (PDF, 1.9 MB).

Weblinks

• Interaktives Java-Applet der Uni Leipzig zur Demonstration
• Ein javascript Interpreter der den Algorithmus auf beliebige Chomsky Grammatiken schrittweise anwendet