Alternative Lösung

Question

Ist es möglich, dass wenn ich die Nonterminalsymbole anders zusammenfasse als in der Lösung (z.B. D -> FA anstatt D -> AF), der CYK Algorithmus nicht mehr funktioniert?

Mit meiner Lösung klappt das Testwort nämlich nicht, in der Musterlösung jedoch schon, dort ist aber schon die Normalform etwas anders als bei mir, da eben die Nonterminalsymbole anders zusammengefasst werden.

 

Vielen Dank!

Answer 1

Hallo ulqgs,

an sich müsste der Algorithmus das Wort akzeptieren, wenn es aus der gegebenen CNF produziert wurde.
Anhand deiner Angaben könnte sich nur der Fehler eingeschlichen haben, dass du am Ende die Regeln, in denen Nonterminalsymbole in Terminalsymbole überführt werden, nicht richtig angepasst hast. Ansonsten reichen die Infos leider für keine tiefer führende Antwort.

Viele Grüße

Moritz (Tutor)