Sprache in CNF - CYK-Algo.

Neue Frage »

Auf diesen Beitrag antworten »
Stefan03 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 smile

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?!?
 
Auf diesen Beitrag antworten »
Karlito

Hallo,

die Grammatik ist nicht in CNF. Deshalb liefert das Applet nicht die richtigen Ergebnisse. Das Applet sieht AB als Nichtterminalsymbol an, obwohl es auch den Nichtterminalsymbolen A und B besteht. Die CNF lässt S->AB CS nicht zu wenn A, B, C und S Nichtterminalsymbole sind.

VG,

Karlito
Auf diesen Beitrag antworten »
Stefan03

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...
Auf diesen Beitrag antworten »
Karlito

Hallo,

die Grammatik ist nicht in CNF, weil z.B. die Produktion S->AB CS zu vier Nichtterminalen führt. Erlaubt sind aber nur genau zwei.

Das Applet akzeptiert die Grammatik, weil es annimmt, dass "AB" ein einziges Nichtterminalsymbol ist welches durch Leerzeichen getrennt von dem weiteren Nichtterminalsymbol "CS" gefolgt wird.

Als Probe kannst du gerne mal versuchen S->A B C S anzugeben. Das führt zu einem Fehler.

Du musst die Grammatik also erst in CNF umformen.

VG,

Karlito
 
Auf diesen Beitrag antworten »
Stefan03

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? smile
Auf diesen Beitrag antworten »
Karlito

Hallo,

habe gerade gemerkt, dass die grammatik doch bereits in CNF vorliegt. Ich habe mich so vertan, weil ich gewohnt bin, dass Alternativen mit einem "|" getrennt werden. Da hätte ich auch eher drauf kommen können, sorry.

Ich habe die Grammatik folgendermaßen in dieses Applet eingegeben:
code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
S -> A B
S -> C S
A -> B C
A -> B B
A -> a
B -> A C
B -> b
C -> A A
C -> B A


Dementsprechend ist dann auch das zu untersuchende Wort "b a b a a a". Danach zeigt das Applet auch eine Lösung an.

VG,

Karlito
Auf diesen Beitrag antworten »
Stefan03 RE: 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...
Auf diesen Beitrag antworten »
Karlito

Sieht so aus als hättest du recht. Ich komme zu dem selben Schluss.
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »