Cocke-Younger-Kasami-Algorithmus

Der Cocke-Younger-Kasami-Algorithmus (oder auch CYK-Algorithmus genannt), ist ein Algorithmus der in der Theoretischen Informatik zur Bestimmung, ob ein Wort zu einer bestimmten kontextfreien Sprache gehört oder nicht, dient. Der Name leitet sich von seinen Entwicklern Itiroo Sakai, John Cocke, Tadao Kasami, Jacob Schwartz und Daniel Younger aus den 1960er Jahren ab. Damit der Cocke-Younger-Kasami-Algorithmus durchgeführt werden kann, muss die vorgegebene Sprache eine Grammatik in Chomsky-Normalform besitzen. Falls dies nicht der Fall ist, muss die Grammatik erst in die Chomsky-Normalform umgewandelt werden. Zur Anwendung kommt beim Cocke-Younger-Kasami-Algorithmus das Prinzip der dynamischen Programmierung, bei der man zu erst die optimale Lösung der kleinsten Teilprobleme direkt berechnet und dann diese zu einer Lösung eines nächstgrößeren Teilproblems zusammensetzt. Dies geht so lange, bis man das Ursprungsproblem gelöst hat.

Für die Anwendung des Cocke-Younger-Kasami-Algorithmus kann man auf unterschiedliche Darstellungen zurückgreifen. Es gibt gestufte Halbfelder oder aber auch eine Pyramidenform, in der man den Algorithmus ausführt. Das Prinzip bleibt aber immer das gleiche.

Beispiel zum Cocke-Younger-Kasami-Algorithmus

Das nachfolgende Beispiel stammt aus der deutschen Wikipedia, allerdings wird hier noch einmal eine andere Darstellungsform verwendet, um die Unterschiede darzustellen. Außerdem wird hier der Algorithmus noch einmal langsam in allen Schritten vorgestellt.

Gegeben sei das Wort w=bbabaa und die Grammatik G= ({S;A;B;C}, {a,b}, P, S). Die Produktionen P der Grammatik sei:
S → AB | BC
A → BA | a
B → CC | b
C → AB | a
Folgend ist nun das Ausgangsdarstellungsschema des Cocke-Younger-Kasami-Algorithmus

Schritt 1 Schritt 2
Im ersten Schritt tragen wir das Wort nach dem unteren Schema ein. Über den ersten Buchstaben lassen wir ein Feld frei, über den zweiten zwei usw. Im zweiten Schritt werden jeweils die grau unterlegten Felder befüllt, also jeweils die Felder über das Zeichen des Worts. Und genau dieses entscheidet. In die grauen Felder kommen nämlich alle Nonterminale/Nichtterminalsymbole aus der oberen Grammatik über die das Zeichen "erreichbar" ist. Für das erste Feld schaut man also nach der Nonterminale, die zu einem b führt. Dies ist laut Grammatik offensichtlich nur bei B → CC | b der Fall, also schreibt man ins Feld ein B. Bei a greift hingegen A → BA | a und C → AB | a, deswegen schreibt man ein A und ein C ins entsprechende Feld.
Schritt 3 Schritt 4
Im dritten Schritt müssen für das Ausfüllen des grauen Kästchens, diesmal nicht nur ein Feld, sondern zwei Felder untersucht werden. In diesem Fall wird nicht nach einem Terminal, sondern nach einem Nichtterminalsymbol gesucht. Nämlich nach dem Nichtterminalsymbol BB (Konkatenation der Terminalsymbole der beiden angrenzenden Felder). Da es dieses Nichtterminalsymbol aber nicht in unserer Grammatik gib, vermerkt man dies im Feld (besser wäre es, wenn man hier die leere Menge reinschreiben würde). Das gleiche Spiel wiederholt sich in Schritt 4. Hier sieht man sich aber mit der Situation konfrontiert, dass es mehrere Möglichkeiten von Konkatenationen gibt. Dementsprechend muss man die Grammatik nach den Nichtterminalsymbolen BA und BC untersuchen. Diese sind beide enthalen, das BC in dieser Regel: S → AB | BC und das BA in dieser Regel: A → BA | a. Dementsprechend schreibt man die zuhgehörigen Nichtterminalsymbole der linken Seite in das Feld, also das S und das A.
Schritt 5,6,7 Schritt 8
Die nachfolgende Schritte wurde zusammengefasst. Es ändert sich nämlich nichts, man schaut sich jeweils die Konkatenationen der Nichtterminalsymbolen an und schaut ob diese in der Grammatik auftauchen. Bei Schritt 8 ist man einmal durch und der nächste Durchgang startet wieder ganz oben. Wie auch schon bei Schritt 3, müssen nun mehr Felder betrachtet werden. Vier sind es nun, wobei die Konkatenationen immer nur zwischen zwei Felder (farblich markiert) gebildet werden. In diesem speziellen Fall ist das erste blaue Kästchen leer (--) dementsprechend müssen nur die gelben Kästchen betrachtet werden.
Schritt 9 Schritt 10
In Schritt 9 geht es wie in Schritt 8 weiter. Gesucht wird nach BS, BC, AB und SB. Die Grammatik kennt AB und BC, dementsprechend werden die zugehörige Nichtterminalsymbole S und C eingetragen. Selbes Vorgehen wie im vorherigen Schritt. Relevant sind ist die Konkationation CC
Schritt 11 Schritt 12
Selbes Vorgehen wie im vorherigen Schritt.
Schritt 13 Schritt 14
Man wird es sich schon denken, im Schritt 13 wird wieder von oben angefangen und es kommen zwei weitere Felder dazu (hier rot markiert). Ansonsten ändert sich allerdings nichts, es müssen lediglich mehr Konkationationen überprüft werden. Selbes Vorgehen wie im vorherigen Schritt.
Schritt 15 Schritt 16
Selbes Vorgehen wie im vorherigen Schritt. Selbes Vorgehen wie im vorherigen Schritt.
Schritt 17 Ergebnis
Letzter Schritt, bei dem noch einmal zwei Felder dazukommen. Was nun im obersten rechten Feld steht, ist das Ergebnis des Algorithmus. Falls das gegebene Wort zur gegebenen Sprache gehört, muss im letzten auszufüllenden Feld oben rechts, das Startsymbol der Grammatik stehen. Dies ist S und man findet es in der rechten oberen Ecke. Damit gehört das Wort zu der gegebenen Sprache.

Weiteres Beispiel im Video

Wer ein weiteres Beispiel zum Cocke-Younger-Kasami-Algorithmus sucht, der sollte sich das nachfolgende Video anschauen, das ich auf YouTube gefunden habe. Hier sieht man noch einmal eine etwas andere Darstellungsform, das Prinzip bleibt aber natürlich das gleiche.

Zitat:



Edsger Wybe Dijkstra:

"Als es noch keine Computer gab, gab es auch das Programmieren als Problem nicht. Als es dann ein paar leistungsschwache Computer gab, wurde das Programmieren zu einem kleinen Problem und nun, wo wir leistungsstarke Computer haben, ist auch das Programmieren zu einem riesigen Problem angewachsen. In diesem Sinne hat die elektronische Industrie kein einziges Problem gelöst, sondern nur neue geschaffen." - The Humble Programmer, ACM Turing Lecture 1972