 Sprache in CNF - CYK-Algo. |
Stefan03
Grünschnabel
Dabei seit: 09.08.2013
Beiträge: 7
 |
|
| 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?!?
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von Stefan03: 10.08.2013 21:09.
|
|
10.08.2013 20:56 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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
|
|
|
11.08.2013 00:50 |
|
|
Stefan03
Grünschnabel
Dabei seit: 09.08.2013
Beiträge: 7
|
|
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...
|
|
|
11.08.2013 15:24 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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
|
|
|
11.08.2013 18:36 |
|
|
Stefan03
Grünschnabel
Dabei seit: 09.08.2013
Beiträge: 7
|
|
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?
|
|
|
12.08.2013 18:36 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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
|
|
|
13.08.2013 18:18 |
|
|
Stefan03
Grünschnabel
Dabei seit: 09.08.2013
Beiträge: 7
|
|
| 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...
|
|
|
14.08.2013 14:35 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Sieht so aus als hättest du recht. Ich komme zu dem selben Schluss.
|
|
|
14.08.2013 15:29 |
|
|
|
