Cocke-Younger-Kasami-Algorithmus

Der Cocke-Younger-Kasami-Algorithmus (CYK-Algorithmus) i​st ein Algorithmus a​us dem Gebiet d​er theoretischen Informatik. Mit i​hm lässt s​ich feststellen, o​b ein Wort z​u einer bestimmten kontextfreien Sprache gehört. In d​er Fachsprache bezeichnet m​an dies a​ls Lösen d​es Wortproblems für kontextfreie Sprachen. Mit Hilfe v​on Backtracking k​ann der Parse-Tree bzw. d​ie Parse-Trees e​ines gegebenen Wortes d​er Sprache konstruiert werden. Um d​en Algorithmus anzuwenden, m​uss zu d​er vorgegebenen Sprache e​ine Grammatik i​n Chomsky-Normalform vorliegen. Der i​n den 1960er Jahren v​on Itiroo Sakai, John Cocke, Tadao Kasami, Jacob Schwartz u​nd Daniel Younger unabhängig voneinander entwickelte Algorithmus n​utzt das Prinzip d​er dynamischen Programmierung.

Beschreibung

Diese Beschreibung f​olgt Hopcroft/Ullman (1996).

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

Gemäß dem Prinzip der dynamischen Programmierung werden erst die ${\displaystyle V_{i,j}}$ für die kleinsten Teilwörter von ${\displaystyle 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 ${\displaystyle w_{i,j}}$, das mehr als nur ein Zeichen enthält, von ${\displaystyle A}$ nur über eine Regel ${\displaystyle (A\rightarrow BC)\in P}$ erzeugt werden. Da Nichtterminale nicht das leere Wort (ε) erzeugen können, muss ${\displaystyle B}$ den linken und ${\displaystyle C}$ den rechten Teil von ${\displaystyle w_{i,j}}$ erzeugen. Daraus folgt:

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

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

${\displaystyle 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: ${\displaystyle w}$ kann genau dann von der Grammatik erzeugt werden, wenn ${\displaystyle S\in V_{1,n}}$ gilt. In ${\displaystyle V_{1,n}}$ liegen alle Variablen, die das Teilwort erzeugen können, das beim ersten Buchstaben anfängt und die Länge ${\displaystyle n}$ hat, also das ganze Wort.

Algorithmus

Aus d​er Beschreibung ergibt s​ich folgender Algorithmus:

Für i = 1 ... n
  Für jede Produktion ${\displaystyle (l\rightarrow r)\in P}$
    Falls r = ${\displaystyle w_{i}}$
      Setze ${\displaystyle 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
      Setze ${\displaystyle V_{i,j}:=V_{i,j}\cup \{l\mid \exists B,C\in N:(l\rightarrow BC)\in P\land B\in V_{i,k}\land C\in V_{i+k,j-k}\}}$
Falls ${\displaystyle 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 ${\displaystyle w=()[()]}$ durch die Grammatik ${\displaystyle G=(\{S,T,U,A,B,C,D\},\{(,),[,]\},P,S)}$ erzeugen lässt. Die Produktionen ${\displaystyle P}$ der Grammatik seien:

${\displaystyle S\rightarrow AB\mid CD\mid AT\mid CU\mid SS}$

${\displaystyle T\rightarrow SB}$

${\displaystyle U\rightarrow SD}$

${\displaystyle A\rightarrow (}$

${\displaystyle B\rightarrow )}$

${\displaystyle C\rightarrow [}$

${\displaystyle D\rightarrow ]}$

Den Algorithmus kann man mittels einer Tabelle durchführen. Dabei ist in der ${\displaystyle i}$-ten Spalte und ${\displaystyle j}$-ten Zeile ${\displaystyle V_{i,j}}$ gespeichert, also die Menge der Nichtterminalsymbole, aus denen sich das Teilwort ableiten lässt, das beim Index ${\displaystyle i}$ anfängt und die Länge ${\displaystyle j}$ hat.

${\displaystyle V_{i,j}}$	1	2	3	4	5	6
1	{A}	{B}	{C}	{A}	{B}	{D}
2	{S}	{}	{}	{S}	{}
3	{}	{}	{}	{U}
4	{}	{}	{S}
5	{}	{}
6	{S}

Da ${\displaystyle S\in V_{1,6}}$, lässt sich das gegebene Wort ${\displaystyle w=()[()]}$ unter der Grammatik ${\displaystyle G}$ aus ${\displaystyle S}$ ableiten.

Eine Linksableitung des Wortes ${\displaystyle w}$ wäre demnach:

${\displaystyle S\Rightarrow SS\Rightarrow ABS\Rightarrow (BS\Rightarrow ()S\Rightarrow ()CU\Rightarrow ()[U\Rightarrow ()[SD\Rightarrow ()[ABD\Rightarrow ()[(BD\Rightarrow ()[()D\Rightarrow ()[()]}$ = ${\displaystyle w}$

Also ist ${\displaystyle w}$ ein Wort der Sprache ${\displaystyle L(G)}$.

Komplexität

Der Algorithmus entscheidet in der Zeit ${\displaystyle {\mathcal {O}}\left(n^{3}\right)}$, ob ein Wort der Länge ${\displaystyle n}$ in der Sprache ${\displaystyle L(G)}$ liegt (vgl. Landau-Symbole zur Beschreibung der Notation). Dabei wird Speicherplatz in der Größenordnung ${\displaystyle {\mathcal {O}}\left(n^{2}\right)}$ 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 (mt-archive.info [PDF]).
• Tadao Kasami: An Efficient Recognition and Syntax-Analysis Algorithm for Context-Free Languages. Air Force Cambridge Research Lab, Bedford 11. Juni 1965 (Scientific report AFCRL-65-758).
• Daniel H. Younger: Recognition and parsing of context-free languages in time n³. In: Information and Control. Band 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 (1. Nachdruck).
• 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 Applet zur Demonstration des CYK-Algorithmus
• Freie Python-Implementierung des CYK-Algorithmus