Thema: Sprache in CNF - CYK-Algo. |
|
Zitat: |
Original von Stefan03
Es kommt wirklich raus, dass babaaa nicht in L liegt.
Aber dann ist doch Teilaufgabe c), in der ich eine Ableitung angeben soll, totaler Schwachsinn, oder?!? |
OK, danke, auf das bin ich mittels "eigener Überlegungen" und auch mit dem anderen Applet gekommen, dass babaaa nicht in L liegt.
Aber kann ich dann Teilaufgabe c) machen. Offensichtlich nicht, oder liege ich da total falsch?
Weil wenn ein Wort nicht in der Sprache liegt, kann ich ja keine Ableitung abgeben...
|
|
Thema: Sprache in CNF - CYK-Algo. |
|
Ok, das leuchtet mir ein...
Aber nun zur Umformung in die CNF...
Da habe ich auch irgendwie Schwierigkeiten...
Ich habe versucht, nach folgenden Beispiel vorzugehen, aber da scheint mir meine CNF doch zu einfach.
Es würde sich nur
S->AA|AS und
A->AA|a|b
ergeben...
Das kanns doch nicht sein, oder?
Es gibt ja die "Kettenregel"
A->B->C->A und somit könnte ich alle B und Cs durch A ersetzen...
Ist das echt so einfach?
|
|
Thema: Sprache in CNF - CYK-Algo. |
|
Hm,
warum ist die Grammatik nicht in CNF?!?
Laut Def. liegt die doch vor, wenn jede Produktionsregel entweder die Form
A->BC oder A->a hat, wobei A,B,C Variablen, sprich Nichterminalsymbole und a ein Terminalsymbol ist.
Und laut diesem Applet einer Uni liegt die Grammatik in CNF vor, aber das Wort ist nicht in L enthalten...
|
|
Thema: Sprache in CNF - CYK-Algo. |
|
Hi,
ich befasse mich gerade mit dem CYK Alg. und ich glaube, ich habe ihn soweit auch gut verstanden. Einem youtube-Video zum Dank
Nun habe ich mich an eine Aufgabe gewagt, von der ich leider keine Lsg. habe. Aus der Aufgabenstellung geht aber wohl hervor, dass das Wort zur Sprache gehört, weil ich Teilaufgabe c) eine Ableitung dafür angeben soll.
in b) Entscheide mittels CYK-Alg, ob w=babaaa zu L gehört.
Im Internet habe ich auch eine Applet gefunden, dass den Alg. durchrechnet und damit wollte ich meinen Fehler finden.
Hierfür muss man aber die Grammatik in CNF eingeben, aber ich bin der Meinung, dass folgende Grammatik bzw. Produktionsregeln in CNF vorliegen:
S->AB CS
A->BC BB a
B->AC b
C->AA BA
Das ist doch die CNF, oder?
Weil wenn ich das im Applet eingebe, kommt eine Fehlermeldung zwecks falscher Syntax...
edit: Ich habe ein anderes Applet gefunden, dass die Eingabe akzeptiert....
Es kommt wirklich raus, dass babaaa nicht in L liegt.
Aber dann ist doch Teilaufgabe c), in der ich eine Ableitung angeben soll, totaler Schwachsinn, oder?!?
|
|
Thema: Endzustand nicht wirklich auch ein Endzustand beim DEA? |
|
Hallo,
ich befasse mich gerade frisch mit dem Thema DEA und habe wohl ein Verständnisproblem zu einem "Endzustand".
Ich würde meinen, dass ein Endzustand ein Zustand ist, von dem aus ein Automat AUF KEINEM FALL mehr "weitermachen" bzw. herauskommen kann.
Aber es scheint wohl nicht so zu sein, sondern ein Endzustand ist dann wohl eben ein Zustand, bei dem der Automat enden kann, oder eben auch nicht.
Sehe ich das richtig?
Siehe diesen DEA im Zustandsdiagramm. Dort gehen auch vom Endzustand q3 Pfeilde weg...
|
|
|