CYK Algorithmus erweitern

[Kirby.exe]

Mein Liebliengsfach ist wieder dran...Alsoo wir sollen den CYK Algorithmus erweitern, dass auch Wörter von Grammatiken mit Ableitungsregeln wie A -> aAB validiert werden können.

Denn der "normale" CYK Algorithmus akzeptiert ja nur Grammatiken, welche in Chompsky Normalform vorliegen. Ich habe mir jetzt seit Stunden den Kopf zerbrochen und gegoogled und leider absolut nur mist gefunden

 

[mihe7]

Mein Liebliengsfach ist wieder dran.

Theoretische Informatik? Nach einiger Zeit läuft man in etwa mit diesem Gesichtsausdruck durch die Gegend

Angst machte mir allerdings, dass ich das irgendwann verstanden habe. Gott sei Dank hat mein Unterbewusstsein dem entgegengewirkt, so dass dieser Zustand nicht von langer Dauer war

Hab jetzt da keine Lust, mich zu vertiefen aber vielleicht kannst Du im Algorithmus vorab die Grammatik einfach umschreiben.

 

[fhoffmann]

Abgesehen davon, dass "theoretische Informatik" fast so schön ist wie "reine Mathematik",
würde ich nicht wirklich folgendes empfehlen:

aber vielleicht kannst Du im Algorithmus vorab die Grammatik einfach umschreiben.

Die Umwandlung einer beliebigen kontextsensitven Grammatik in Chomski-Normalform ist doch sehr komplziert (und ich vermute mal, dass selbst die Umformung einer Grammatik, die A -> aBC erlaubt, in Chomski-Normalform immer noch kompliziert ist).

Ich würde eher empfehlen, mir den CYK-Algorithmus genauer anzugucken und diese Erweiterung einzubauen.

Aber das ist nur ein vages Gefühl und ich habe keine wirkliche Lösung.

 

[fhoffmann]

und ich vermute mal, dass selbst die Umformung einer Grammatik, die A -> aBC erlaubt, in Chomski-Normalform immer noch kompliziert ist

Ich muss mich korrigieren:
Die Umwandlung einer Grrammatik der Form
A -> aBC
ist möglich durch eine neue Grammatik der Form (in Chomski-Normalform):
A -> XY
X -> a
Y -> BC

Somit ist der Ansatz von @mihe7 möglicherweise doch umsetzbar.

Dennoch bleibt mein Vorschlag natürlich stehen, dass ich den CYK-Algorithmus anpassen würde.

 

[mihe7]

Abgesehen davon, dass "theoretische Informatik" fast so schön ist wie "reine Mathematik",

Oh, da will ich gar nicht widersprechen. Meine Aussage war auf das Studium bezogen, da hängt es dann wohl stark vom Dozenten ab. Wenn Du null Erklärungen sondern nur Formeln und Beweise um die Ohren gehauen bekommst und in jeder(!) Aufgabe, mit der Du dann das nicht vermittelte Wissen üben sollst, Fehler enthalten sind, die Dich Tage an Zeit kosten, dann kotzt Dich das irgendwann nur noch an. Die Aussage von @Kirby.exe bzgl. des "Lieblingsfachs" kann ich sehr gut nachvollziehen, auch wenn ich heute natürlich einen anderen Blick auf die TI habe. Das geht so weit, dass ich mir sogar vorgenommen habe, mich aus Spaß an der Freud' mal wieder intensiver damit zu beschäftigen Aber wenn, dann von vorne mit gescheitem Material.

 

[Kirby.exe]

Hab jetzt da keine Lust, mich zu vertiefen aber vielleicht kannst Du im Algorithmus vorab die Grammatik einfach umschreiben.

Leider war ebenfalls Bedingung, dass die Grammatik vor Anwendung des Algorithmus nicht in Chomsky Normalform umgeformt werden darf...Also muss wirklich der Algorithmus an sich angepasst werden

 

[Kirby.exe]

Ich würde eher empfehlen, mir den CYK-Algorithmus genauer anzugucken und diese Erweiterung einzubauen.

Aber das ist nur ein vages Gefühl und ich habe keine wirkliche Lösung.

Well there is our Problem xD Ich habe mir das Ding jetzt ewig angeschaut und keinen blassen Schimmer

 

[Kirby.exe]

Oh, da will ich gar nicht widersprechen. Meine Aussage war auf das Studium bezogen, da hängt es dann wohl stark vom Dozenten ab. Wenn Du null Erklärungen sondern nur Formeln und Beweise um die Ohren gehauen bekommst und in jeder(!) Aufgabe, mit der Du dann das nicht vermittelte Wissen üben sollst, Fehler enthalten sind, die Dich Tage an Zeit kosten, dann kotzt Dich das irgendwann nur noch an. Die Aussage von @Kirby.exe bzgl. des "Lieblingsfachs" kann ich sehr gut nachvollziehen

Du sprichst mir aus der Seele xD Der Prof kennt sein Themengebiet sehr gut und das ist auch schön, aber didaktisch könnte das ein kleines Kind besser...xD Die Vorlesung ist mist und das Skript eine einzige Formelsammlung und wirkliche Erklärungen