Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
CYK
Servus. In den Altklausuren wurde desöfteren nach der rekursiven Definition des CYK-Algorithmus gefragt.
V(i,i) =
V(i,j) =
Wie müssen die zwei Zeilen lauten? Finde da nichts.
Danke schonmal und viel Erfolg bei der klausur am Montag 
In diesem Braindump gibt es was dazu, Aufgabe 5:
https://fsi.cs.fau.de/repo_public/klausuren/bfs/2011-04-29_braindump+loesung.pdf
(Lässt sich nur nicht schön hier ein kopieren)
Muss in der letzten Klausur https://fsi.cs.fau.de/dw/_media/pruefungen/grundstudium/bfs_2015-02-03_braindump.pdf (WS14-15) statt V(2,4) → V(2,5) stehen?
Kann mir jemand helfen, wie ich einen Syntaxbaum aus der CYK-Tabelle bauen kann? Ich habe kein Algorithmus im Internet oder so gefunden.
Z.B. in der letzten Klausur hab ich für V(1,5) = V(2,5) = {S,A,C} gekriegt. Wie muss ich jetzt weiter gehen? Und gibt es nur eine mögliche Variante des Baums oder mehrere? Danke.
Danke David24
@yef:
Für den Ableitungsbaum muss man im Endeffekt nur das S zurückverfolgen:
S kann nur aus AB oder BC entstehen, jetzt schaust halt aus welchen 2 Stellen das S in V(1,5) entstanden ist. Wenn es mehrere Möglichkeiten gibt, suchst dir eine aus.
In dem Fall des 2015 Braindumps kommt das S von BC, das durch V(1,5) und dem B gleich unter dem kleinen b (müsste dann 1,1 sein?)
Also von S zwei Zweige: B und C. Dasselbe dann für das B und C etc.
Ah cool! Danke dir!
Ich hab so gelöst.
jop habe ich genauso