Cocke-Younger-Kasami-Algorithmus: Vorgehensweise

Question

Man soll überprüfen, ob das Wort $w = bbaaab$ durch die angegebene Grammatik erzeugt werden kann. Wie die Tabelle erstellt wird, weiß ich. 

Für Zeile $m = 1$ suche ich alle Ableitungen, die in einem Schritt von Nonterminal- auf Terminalsymbol ableiten. Ich trage die jeweiligen Nonterminalsymbole in ihre Zellen ein.

Für die Zeilen ab $m = 2$ muss ich jetzt alle Ableitungen suchen, die auf mehrsymbolige Teilwörter ableiten. Mir ist jetzt nicht mehr klar, was ich hier überprüfen muss. Wieso steht z.B. in der Zelle von Zeile $m = 2$ und dem ersten b nichts, aber dafür in der Zelle rechts daneben? Wie muss ich hier vorgehen?

 

Für eine Erklärung wäre ich sehr dankbar!

Comments

Nur der Vollständigkeit halber: Es ist sehr schön, dass Sie sich den CYK-Algorithmus anschauen - es ist ein netter Algorithmus mit viel Erkenntnisgewinn. Allerdings ist er seit letzem Jahr nicht mehr Teil des Vorlesungsstoffs und kommt in der Klausur nicht dran.

---

Die Aufgabennummer "Kapitel 6 Aufgabe 57" müssen Sie nicht angeben, die ID KON-AE reicht (und ist eindeutig; die Aufgabennummer kann sich über die Zeit ändern).

Answer 1

Sehr schöne und ausführliche Antwort von Ashvin, vielen Dank dafür! 

Nur zwei kleine Fehler haben sich in den angegebenen Pseudocode eingeschlichen: Das j in den Deklarationen von i und k muss durch m ersetzt werden, es bezeichnet die Zeilen der Tabelle. 
Des weiteren bezeichnet F(i,m) das i-te Feld von links in der m-ten Zeile (nicht Spalte).

Und für alle, denen es wie mir geht und die durch die vielen Indizes und Laufvariablen total verwirrt sind: Ein kleines Bild, das zeigt, aus welchen Feldern die Symbole miteinander kombiniert werden, am Beispiel von Feld F(4,2). Es werden alle Symbole eingetragen, aus denen BS, BA, BC (1), SB, AB (2), A, C (3) abgeleitet werden können.

 

Viele Grüße,

Micaela Wünsche

 

Answer 2

Hey utdtz,

Da der Cocke-Younger-Kasami-Algorithmus als Eingabe neben dem zu überprüfenden Wort eine Grammatik in Chromsky-Normal-Form benötigt, haben sämtliche Regeln die Form NxT (ein Terminalsymbol rechts) oder NxNN (zwei Nonterminalsymbole rechts).

Die Regeln der Form NxT sind für den Algorithmus für m=1 relevant. Dort hast du die Schritte auch richtig nachvollzogen.

Ab m=2 läuft der Algorithmus etwas anders ab:

for m=2 to n do                                   (m läut alle Zeilen durch)
    for i = 1 to n-j+1 do                         (i läuft alle Spaten in der Zeile m durch)
       F(i,m) = Ø                                    (In Spalte i und Zeile m zuerst keine Werte)
       for k=1 to j-1
          F(i,m) = F(i,m) U {X | X → YZ ist Regel in P mit Y ist Nonterminalsymbol in                                                    V(i,k) und und Z ist Nonterminalsymbol                                                    in V(i+k,j-k)}

Anmerkung: Mit F(i,m) meine ich das i-te Feld von links für die Spalte m.
 

Für das erste Feld in Zeile 2 (F(1,2)) überprüft man nach dem Algorithmus ob es Regeln gibt, die ein Nonterminalsymbol auf BB ableiten. (Erstes B aus F(1,1) zweites B aus F(2,1)). Da es keine gibt wird dies hier mit einem Strich notiert.

Für das zweite Feld in Zeile 2 (F(2,2)) überprüft man ob es Regeln gibt die ein Nonterminalsymbol auf BA oder oder BC ableiten(B aus F(2,1) und A bzw. C aus F(3,1)). Es gibt zwei Regeln, für welche dies erfüllt ist. Die Nonterminalsymbole auf der linken Seite der Regeln lauten S,A welche dann in das Feld eingetragen werden.

Hinweis: Es werden nicht immer die zwei Felder über bzw. recht über dem dem auszufüllenden Feld betrachtet. Ab der dritten Zeile (m=3) wird das beim Ausführen des Algorithmuses deutlich. Daher am besten den Algorithmus einige male nach der Definition ausführen, dann hat man relativ zügig auch die Reihenfolge der zu betrachtenden Felder nachvollzogen :)

Falls trotz meiner langen Antwort Fragen offen bleiben oder etwas unklar ist, frag hier gerne nochmal nach!

Ashvin (Tutor)