Theoretische Informatik

Der CYK-Algorithmus (benannt nach den Autoren Cocke, Younger und Kasami) löst das Wortproblem für kontextfreie Sprachen. Es wird kein Stackautomat verwendet. Die Zeitkomplexität des Algorithmus liegt in O(n³). Die kontextfreie Grammatik muss in Chomsky-Normalform vorliegen.

Idee

Gegeben sei eine Grammatik G = (V, T, P, S) in Chomsky-Normalform und ein Wort w = w₀ ... w_n-1  ∈  T *. Das Wort lässt sich in folgenden zwei Fällen aus einer Variablen Z ableiten:

• es besteht aus einem einzigen Terminalzeichen w₀ und die Produktion Z → w₀ existiert   oder
• es besteht aus zwei Teilwörtern w₀, ..., w_k-1 und w_k, ..., w_n-1 , die sich aus den Variablen X bzw. Y ableiten lassen und die Produktion Z → XY existiert (Bild 1).

Um zu entscheiden, ob die zweite Bedingung erfüllt ist, werden alle möglichen Trennstellen k ∈ {1, ..., n-1} zwischen den beiden Teilwörtern betrachtet und die Teilwörter nach denselben beiden Kriterien untersucht.

Zunächst liegt es nahe, einen rekursiven Algorithmus zur Implementation dieser Idee in Betracht zu ziehen. Es stellt sich jedoch heraus, dass ein rekursiver Algorithmus viele Berechnungen unnötig mehrfach durchführt. Die Berechnung, aus welchen Variablen sich ein Teilwort w_i, ..., w_j-1 ableiten lässt, wird für jedes längere Teilwort, dessen Bestandteil es ist, erneut ausgeführt.

Effizienter ist es, diese Berechnung nur einmal auszuführen und das Ergebnis zu speichern, sodass es bei Bedarf wiederverwendet werden kann. Dieser Gedanke führt zu einem Algorithmus nach der Methode der "dynamischen Programmierung".

Algorithmus

Bei der Methode der dynamischen Programmierung werden zunächst die Berechnungen für alle Teilwörter der Länge 1 durchgeführt, dann für alle Teilwörter der Länge 2, 3, usw. Die Ergebnisse werden in einer Tabelle gespeichert und bei jedem weiteren Schritt wiederverwendet.

Sei eine Grammatik G und ein Wort w = w₀ ... w_n-1 gegeben. Wir betrachten die Teilwörter w_i,k von w, die an Position i beginnen und die Länge k haben, d.h. w_i,k  =  w_i ... w_i+k-1.

Für jedes Teilwort w_i,k ist ein Feld in der Tabelle vorgesehen; dort wird die Menge der Variablen V_i,k gespeichert, aus denen sich w_i,k ableiten lässt (meist ist dies nur eine Variable, es können aber auch mehrere sein).

Die Tabelle wird spaltenweise berechnet. Die Variablenmengen V_i,1 in Spalte 1 bestehen aus den Variablen, aus denen sich das daneben befindliche Wort der Länge 1 ableiten lässt. So enthält beispielsweise V_3,1 die Variable Y, weil sich b aus Y ableiten lässt (Bild 2 a).

Die Variablenmengen V_i,k in den anderen Spalten werden aus den schon gefüllten Feldern derselben Zeile und der darunter liegenden Diagonalen berechnet (Bild 2 b). Es werden die Produkte V_i,jV_i+j,k-j gebildet. Enthält das Ergebnis die rechte Seite einer Produktion, so wird die zugehörige linke Seite in die Variablenmenge V_i,k aufgenommen.

So kommt beispielsweise die Variable S in die Variablenmenge V_1,4, weil das Produkt V_1,1V_2,3 die rechte Seite der Produktion SXZ enthält.

Wenn zum Schluss im rechten oberen Eckfeld das Startsymbol S enthalten ist, so wird das Wort w erkannt, d.h. es gilt

w = w₀, ..., w_n-1  ∈  L(G)    ⇔    S ∈ V_0,n

Beispiel:  Gegeben sei eine Grammatik G mit den Produktionen

S		XY  |  XZ
Z		SY
X		a
Y		b

und das Wort w = aaabbb. Der CYK-Algorithmus erzeugt folgende Tabelle:

 

 

Bild 2: Tabelle des CYK-Algorithmus für die Grammatik G und das Wort w = aaabbb

 

Programm

Folgendes Programm implementiert den CYK-Algorithmus. Gegeben ist eine Grammatik G = (V, T, P, S) in Chomsky-Normalform und ein Wort w ∈ T * der Länge n. Gefragt ist, ob sich w in G ableiten lässt, ob also w ∈ L(G) ist.

Als Vorbereitung für den Algorithmus wird eine Tabelle mit n Zeilen und n+1 Spalten angelegt und in Spalte 0 zeichenweise das Wort w eingetragen.

Der Algorithmus benutzt die Funktion leftSidesOf(v), um die linken Seiten aller Produktionen zu ermitteln, die das in der Menge v befindliche Terminalzeichen als rechte Seite haben. Ferner benutzt er die Funktion leftSidesOfCombinationsOf(u, v), um die linken Seiten aller Produktionen mit der rechten Seite XY zu ermitteln, wobei X in der Menge u und Y in der Menge v enthalten ist.

CYK-Algorithmus

Eingabe:

Grammatik G in Chomsky-Normalform mit Startsymbol S,
n × n+1-Matrix V, in deren Spalte 0 ein Wort w der Länge n steht

Ausgabe:

true, falls w ∈ L(G), false sonst

Methode:

Analyse

Der CYK-Algorithmus legt für ein Wort der Länge n eine Tabelle mit O(n²) Feldern an. Die Einträge in den Feldern werden in jeweils O(n) Schritten berechnet.

Der CYK-Algorithmus hat also eine Platzkomplexität von O(n²) und eine Zeitkomplexität von O(n³).

Literatur

[Web 1]   http://de.wikipedia.org/wiki/CYK-Algorithmus   Artikel in Wikipedia