Ableitungsbaum
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-Algo
Den CYK-Algo hab ich soweit verstanden und auch angewendet und meine Tabelle ist voll. S \in V(1,n), also mein Wort auch aus der Sprache, aber wie kann ich jetzt schnell und effizient den Ableitungsbaum herleiten?
Mein Problem ist:
Ich fange mit S an, nun muss ich mich schon entscheiden welche Teilwörter ich betrachte. V(1,4) und V(5,5) oder V(1,3) und V(4,5) oder … usw.
Alle Wege auszuprobieren wäre meiner Meinung nach ziemlich ineffektiv, geht das schneller?
Das habe ich vor ein paar Tagen auch googeln müssen.
Aber hübsche Anleitungen habe ich auch nicht gefunden.
Im Prinzip funktioniert es so:
Du beginnst bei V(1,n) und der optimale Fall wäre es, wenn du eine Regel S → BC hast, wobei B in der Tabelle V(1,1) steht und C in V(2,n). Dann kannst du mit dem B direkt das erste w1 erzeugen. Mit C wiederholst du dann das Spiel: hast du eine Regel C → EF, wobei E in der Tabelle an Stelle V(2,2) steht und F an Stelle V(3,n)? […] Das wird aber wahrscheinlich nicht immer der Fall sein. Ansonsten musst du dir deinen Weg in der Tabelle suchen. Ich schätze, da muss man dann ein bisschen Übung haben, die Wege schnell zu finden, wenn man sie sich nicht mitaufgeschrieben hat.
Ok, also brauch man ne kleine Portion Glück um schnell zu sein 
Wobei die Tabellen in den Altklausuren sich immer in Grenzen gehalten haben.
Genau das ist der Punkt. Beim Aufstellen der Tabelle kannst du jeweils dazu notieren wo du her kommst, dann geht der Rückweg schnell.
Asymptotisch gibt sich das allerdings glaube ich nichts, CYK ist eben ziemlich aufwendig…
[s]https://mega.co.nz/#!PNJDwKDZ!Yhr4pAOyxrwi4GU9IMPrvzxKFdJ0EM6leqlLk7mS2Y[/s]
Einfache Erklärung…
Edith: http://www.youtube.com/watch?v=JugIgxUyA4Q selbes Video
Die Nummerierung der Zeilen ist im Skript (bzw meiner und der Mitschrift eines Komilitonen) fehlerhaft.
Es müsste doch eigentlich 1 bis n und nicht 0 bis n lauten - sonst hätte man ja z.b V(1,0) oder ?
Wenn du wissen möchtest ob w \in L(G), dann muss S \in V(1,|w|) sein.
Das dacht ich mir auch.
Ja das war einigen Personen auch schon in der Vorlesung klar. Aber keiner hatte Lust/Energie den Zorn des Dozenten auf sich zu ziehen ;).
Dafür den Missmut der Studenten? ô.O
Nein ernsthaft. Wenn es auffällt, warum dann nicht auch sagen?
Entschuldigung, manchmal sind meine Motive nicht optimal ;).
Und den anderen geht das wahrscheinlich ähnlich.
Bringt Herrn Wanka ja auch nichts wenn er diesen Minifehler immer weiterschleppt - irgendwann lernt das ein Student und verhaut den Algorithmus dadurch.
ist zur durchführung des algos nicht der Tablellenaufbau selbsterklärend… es ist doch nur nach rekursiver definition gefragt, und da muss ich ja eigentlich nicht dazusagen, dass 1< i,j < |w| Oder?
Klar, ist nicht zwingend notwendig. Aber wenns richtig drin steht ists eben besser 
Also für mich war das in der Vorlesung nicht mehr als eine Nummerierung der Zeilen, die mit den Vs nichts weiter zu tun hat. Wenn man bei 1 anfängt passt es natürlich besser.
O wei, na hoffentlich legt sich das bis zur Korrektur wieder 
Muss fast, wenn ich das linke Smiley richtig interpretiere wuerden die Klausuren sonst direkt Feuer fangen. :scared:
Jetzt muß ich doch mal fragen, was Sie konkret meinen.
In meiner Vorlesungsausarbeitung steht an der Stelle, an der ich die Tabelle für die V(i,j) einführe:
Kontruktion der V(i,j) nach der Länge ell =j - i
a[sub]1[/sub] a[sub]2[/sub] a[sub]3[/sub] ...
0 V(1,1) V(2,2) V(3,3) V(4,4) V(5,5) …
1 V/1,2) V(2,3) V(3,4) …
2 …
3 …
4 V(1,5)
Die Werte für ell stehen in der ersten Spalte, und da ell als j - i definiert ist, beginnt die Numerierung in der Tat bei 0.
Ist es das, was zur Verwirrung führte? 
MfG
Rolf Wanka
Die Verwirrung rührt daher, dass in der Vorlesung an der Tafel in der letzten Zeile ganz links ein n, in Ihrem Beispiel also 5 stand.
Ziemlich banal… Und außerdem harmlos, da sowas bei der Durchführung, also wenn man alle Zeilen dazwischen ausfüllt, sicher nicht passieren wird.