Original von AnyKey
Ich frage mich, wie man nach Anwendung des CYK-Algorithmus' (S.25-26) von der entstandenen Tabelle auf die Ableitungsbäume kommt.
Wir suchen einen Ableitungsbaum für x = baaba. Da S \in T(1, 5) gilt, ist x \in L(G). Es gibt demnach mindestens einen Ableitungsbaum für x, der vom Startsymbol ausgeht.
Aus S können nur AB und BC erzeugt werden. Diese beiden Fälle untersuchen wir:
Fall 1 (S => AB).
Ist dies der erste Ableitungsschritt, so gibt es eine Zahl k mit 1 <= k < 5, für die gilt A =>* x_{1, k} und B =>* x_{k + 1, 5}. Wir prüfen nun alle möglichen Werte für k durch, ob es eine solche "passende" Ableitung gibt. Zunächst prüfen wir also k = 1, also ob A =>* b und B =>* aaba gilt. Dies ist laut Tabelle nicht der Fall, also prüfen wir k = 2. Hier sind wir erfolgreich, denn es gilt A \in T(1, 2) und B \in T(3, 3). Für k = 3 und k = 4 erhalten wir keine Lösung. Demnach gibt es genau einen Ableitungsbaum für x, dessen erster Schritt S => AB ist.
Fall 2 (S => BC)
Hier gehen wir genauso vor wie oben und erhalten, daß nur k = 1 eine Lösung ist.
Setzt man dieses Vorgehen rekursiv fort, so erhält man schließlich einen (wenn man möchte auch alle) Ableitungsbaum (-bäume) für x.