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 | BCFolgend ist nun das Ausgangsdarstellungsschema des Cocke-Younger-Kasami-Algorithmus
A → BA | a
B → CC | b
C → AB | a
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. |