# CYK Algorithmus erweitern



## Kirby.exe (26. Mai 2021)

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 (26. Mai 2021)

Kirby.exe hat gesagt.:


> 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 (26. Mai 2021)

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


mihe7 hat gesagt.:


> 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 (26. Mai 2021)

fhoffmann hat gesagt.:


> 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 (27. Mai 2021)

fhoffmann hat gesagt.:


> 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 (27. Mai 2021)

mihe7 hat gesagt.:


> 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 (27. Mai 2021)

fhoffmann hat gesagt.:


> 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 (27. Mai 2021)

mihe7 hat gesagt.:


> 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


----------

