Fachrat Informatik - Forum

Hi,
ich poste mal meine Frage zum Skript hier hinein.

Ich frage mich, wie man nach Anwendung des CYK-Algorithmus' (S.25-26) von der entstandenen Tabelle auf die Ableitungsbäume kommt.

Ich weiss, dass sich die Anzahl der mögl. Ableitungen aus der Anzahl der Vorkommen des Startsymbols in T[1, 5] ergibt. Auch wenn 'S' eigentlich nur einmal in T[1, 5] vorkommen kann.

-Danke-

Quoted

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.