View Full Version : Beispiel 4.2
schrankk
01-11-2008, 18:57
bei mir kam es bei dieser Aufgabe zu ziemlich viel Schreiberei!! :o
Am Ende ergab sich die Menge von Nonterminale N={S, A, B, Xa, Xb, Y1, ..., Y9}. Ist es bei euch auch irgendwie so ähnlich?
P.S
leider hab ich kein Scanner, und meine ganze Lösung abzutippen wäre viel zu aufwendig, sorry...
http://liinwww.ira.uka.de/~rahn/cnf/ (http://liinwww.ira.uka.de/%7Erahn/cnf/)
ich komm aber nur bis Y4 (bzw. bis 3, weil Y2 und Y4 bei mir gleich sind)
wie entfernt man die Regel, bei der S auf der rechten Seite steht? (was ja in chomsky normalform nicht sein darf, da S -> epsilon)
wie entfernt man die Regel, bei der S auf der rechten Seite steht? (was ja in chomsky normalform nicht sein darf, da S -> epsilon)
S' einführen und auf alle Produktion von S produzieren lassen. Zusätzlich \eps dazu. S und dessen Produktionen darfst aber nicht entfernen.
1 Entfernung von nutzloser Prod.
2 Überprüfen, ob alle Symbole vom S aus erreichbar sind.
3 Elimination der E- Produktionen
S-> AB
A-> aA l a
B-> b l bb l aA l a
4 Elimination von Einheitsproduktionen (B->A)
S-> AaA l Aa
A-> aA l a
B-> b l bb l aA l a
5 Ersetze a durch Xa in allen Produktionen in denen a nicht alleine auf der rechten Seite vorkommt
S-> AXaA l AXa
A-> XaA l a
B -> b l XbXb l XaA l a
ist es richtig bis hierher und wie geht es weiter ?
danke!!
ist es richtig bis hierher und wie geht es weiter ?
ne, ist es nicht. Schon beim 1. Schritt von dir darfst du das S nicht weg löschen. Benutz am besten die URL von mir oben und denk Schritt für Schritt mit.
Bianconeri
04-11-2008, 16:29
Ich habe wie manül auch nur 4 verschiedene Y. Davon ist allerdings die Produktion auf AS doppelt. Wenn man die zusammenfasst, was man ja eigentlich dürfen müsste habe ich auch 3 verschiedene Y.
Produktionen habe ich übrigens 19 bzw. 18 wenn man die 2 zusammenfasst.
@manül
Kannst du bitte noch mal erklaeren, wie man S von der rechten Seite entfernen kann.
Bei mir ist es so;
B->a
B->b
S->AB
A->a
Xa->a
B->XaA
A->XaA
Xb->b
B->XbS
B->SXb
B->XbXb
S->AY1
Y1->SB
B->XaY2
Y2->AS
A->XaY3
Y3->AS
B->SY4
Y4->XbS
und wie geht es weiter ?
mfg
Bianconeri
04-11-2008, 18:07
@manül
Kannst du bitte noch mal erklaeren, wie man S von der rechten Seite entfernen kann.
Bei mir ist es so;
B->a
B->b
S->AB
A->a
Xa->a
B->XaA
A->XaA
B->Xb
Xb->b
B->XbS
B->SXb
B->XbXb
S->AY1
Y1->SB
B->XaY2
Y2->AS
A->XaY3
Y3->AS
B->SY4
Y4->XbS
und wie geht es weiter ?
mfg
Gut dass du das fragst. Das Leerwort hätte ich glatt vergessen. Habe die selben Produktionen wie du nur dass ich B->Xb nicht habe. Die darf nämlich gar nicht auftreten, weil sie nicht von der Form A->BC oder A->a ist.
Al Kupone
04-11-2008, 18:22
nicht auf die eine CNF-maschine verlassen, die gibt andere ergebnisse, hab das bsp vom skriptum ausprobiert u kommt was ganz anderes raus!!
was einheitsproduktionen angehen:
B -> ..bS|b|A|bb ..wie man sehen kann, kann B zu A werden..gilt hier die Einheitsproduktion oder wird ignoriert? denn, wenn man sie gelten lässt, dann verschwindet die ableitung zu B beim pkt S, denn alle Bs werden ja zu den werten von A. U soviel ich weiß, es kommt doch kein ε wenn auf der rechten seite ein S ist, u hier ist das der fall..oder irre ich mich??
U soviel ich weiß, es kommt doch kein ε wenn auf der rechten seite ein S ist, u hier ist das der fall..oder irre ich mich??
Doch aber brauchst ein neues Startsymbol. Also S' mit allen Produktionen von S + zu ε.
Bianconeri
04-11-2008, 18:31
nicht auf die eine CNF-maschine verlassen, die gibt andere ergebnisse, hab das bsp vom skriptum ausprobiert u kommt was ganz anderes raus!!
was einheitsproduktionen angehen:
B -> ..bS|b|A|bb ..wie man sehen kann, kann B zu A werden..gilt hier die Einheitsproduktion oder wird ignoriert? denn, wenn man sie gelten lässt, dann verschwindet die ableitung zu B beim pkt S, denn alle Bs werden ja zu den werten von A. U soviel ich weiß, es kommt doch kein ε wenn auf der rechten seite ein S ist, u hier ist das der fall..oder irre ich mich??
Da kommt was anderes raus, weil die Epsilon Produktion fehlt. Sonst stimmt das Ergebnis der CNF Maschine.
Al Kupone
04-11-2008, 18:32
was ist mit der einheitsproduktion..gilt das a in diesem fall oder nicht?
Soll es so aussehen ?
S' -> AB l AY1 l e
Y1 -> SB
...
...
...
usw..
Al Kupone
04-11-2008, 18:33
nicht ganz, denn selbst wenn epsilon geschrieben wird, übernimmt die maschine das C, obwohl im buch es eliminiert wird.
Bianconeri
04-11-2008, 18:41
Ist das mit dem S' einführen so gemeint?
{S'->Epsilon | AY1 | AB, S->AB | AY1, Y1->SB ................. }
Al Kupone
04-11-2008, 18:46
menno, kann jemand das mit der einheitsproduktion erklären oder habt ihr alle nur von der maschine abgeschrieben?i meins net böse,aber ich komm da net weiter um im großen u ganzen komme ich auch auf 3 Ys.
Ist das mit dem S' einführen so gemeint?
{S'->Epsilon | AY1 | AB, S->AB | AY1, Y1->SB ................. }
So hätt ichs gemeint. Aber wieso hast die Reihenfolge der Produktionen extra vertauscht ? :confused:
Bianconeri
04-11-2008, 19:07
So hätt ichs gemeint. Aber wieso hast die Reihenfolge der Produktionen extra vertauscht ? :confused:
Was meinst du mit Reihenfolge der Produktionen vertauscht? S' hab ich am Anfang weils ja das neue Anfangssymbol ist.
S'-> AB l AY1 l Epsilon ,
S-> AB l AY1 l ,
B-> a l b l XaA l SXb l XbS l XbXb l XaY2 l SY4,
A-> a l XaA l XaY3,
Xa->a,
Xb->b,
Y1->SB,
Y2->AS,
Y3->AS,
Y4->XbS
wie schaut es aus ?
Was meinst du mit Reihenfolge der Produktionen vertauscht? S' hab ich am Anfang weils ja das neue Anfangssymbol ist.
{S'->Epsilon | AY1 | AB, S-> AY1 | AB, Y1->SB ................. }
So sieht man sofort, das bei S' nur Epsilon dazu gekommen ist.
Bianconeri
04-11-2008, 19:19
{S'->Epsilon | AY1 | AB, S-> AY1 | AB, Y1->SB ................. }
So sieht man sofort, das bei S' nur Epsilon dazu gekommen ist.
Achso ok das war nicht beabsichtig.
Al Kupone
04-11-2008, 21:59
meine lösungen..in 2 versionen. bei der einen hab ich die einheitsproduktionsregeln (laut buch) verwendet, beim anderen nicht..ist sicher falsch,aber da keiner sich irgendwie richtig auskennt,ist es besser als nix :devil::D
@ Al Kupone
Deine Loesungen sind nicht lesbar :) Kannst du bitte dein P' noch mals schreiben.
mfg
@manül
Wenn ich das Beispiel,das in den Folien stehen (Seite 89), mit von dir gesendete Link loesen will, dann bekomme eine veschiedene Loesung .
Das Problem liegt in dem Nicht- Kette Section.
zB: S->aA l B , A->aB l a , B ->A
=>
S->aA l aB l a , B-> aB l a , A->aB l a
aber es soll wie unten sein !!
S->aA l aB l a , B-> aB l a , A->aaB l aa l a
google "chomsky normalform asb aAs sbs bb"
jperl
schrankk
05-11-2008, 17:23
google "chomsky normalform asb aAs sbs bb"
jperl
na so was!! :shinner:
schrankk
05-11-2008, 17:56
und ich habe endlich meinen Fehler gefunden!!
Also im 4. Schritt, wo es um Elimination von Einheitsproduktionen geht, ersetzen wir in unserem Beispiel B->A durch B->a|aA|aAS. Nun die Frage: tun wir es nur für B->A, oder für alle Vorkommnisse von B auch in anderen Produktionen??
So wie ich es nun verstanden habe, ersetzen wir in unserem Beispiel in Produktionen S->ASB und S->AB das Symbol B nicht durch oben genannte (B->a|aA|aAS)... aber wieso nicht?? In Beispiel aus Folien werden z.B. auf Seite 96 doch ALLE Vorkommnisse von B ersetzt!!
hat da jemand paar Tipps für mich?
das habe ich mich auch schon gewundert. wenn ich mich aber recht erinnere, gibts aber beim beispiel im skriptum zusätzlich eine einheitsabbildung S -> B oder?
somit hätte ich S -> B -> A und muss in S auch alles ersetzen.
jperl
Al Kupone
05-11-2008, 18:29
also, ich hab nur das getan, was im skriptum steht u zwar alles was B -> A, A -> ... ersetzt, was blöderweise dazu führt, dass der zugang zu B verschwindet. bin jetzt drauf gekommen, dass dann der S -> ...schritt viel länger wird, weil ja das B im S durch alle B variablen ersetzt wird...zwar bleibt b aber B verschwindet und erhalten am ende nur S,A als nonterminale.u es freut mich zu wissen, dass endlich einige draufkommen, dass das mit der einheitsproduktion etwas komplizierter ist!! ^^
schrankk
05-11-2008, 18:30
das habe ich mich auch schon gewundert. wenn ich mich aber recht erinnere, gibts aber beim beispiel im skriptum zusätzlich eine einheitsabbildung S -> B oder?
somit hätte ich S -> B -> A und muss in S auch alles ersetzen.
jperl
ganz genau, es gibt noch S->B in diesem Beispiel... Also auch eine Einheitsproduktion, auf die (im gegensatz zu B->A) leider nicht aufmerksam gemacht wurde!! :(
Einiges verstehe ich aber immer noch nicht! Das Vorkommnis von B in der Produktion A->aB wird eben auch ersetzt... und von A ausgehend gibt es schon sicher keine Einheitsproduktion A->B!! :o
Edit: hab so bisschen darüber nachdeacht und bin zum für mich beruhigenden Schluß gekommen, dass es einfach ein kleiner Fehler in Skriptum vorgekommen ist, da dieses kleine Ersetzen absolut kein Sinn macht... sonst hab ich ganze Verfahren endlich kapiert!! :cool:
schrankk
05-11-2008, 18:40
also, ich hab nur das getan, was im skriptum steht u zwar alles was B -> A, A -> ... ersetzt, was blöderweise dazu führt, dass der zugang zu B verschwindet. bin jetzt drauf gekommen, dass dann der S -> ...schritt viel länger wird, weil ja das B im S durch alle B variablen ersetzt wird...zwar bleibt b aber B verschwindet und erhalten am ende nur S,A als nonterminale.u es freut mich zu wissen, dass endlich einige draufkommen, dass das mit der einheitsproduktion etwas komplizierter ist!! ^^
Zugang zu B verschwindet genau deswegen nicht, da die Produktionen S->ASB und S->AB unverändert bleiben!!
vlg
Al Kupone
05-11-2008, 18:43
also, soweit ich das verstanden habe, werden alle Bs durch diese produktion (B -> A -> ..) ersetzt, deswegen wird im skriptum a die A produktion länger, aber da die A produktion selbst ein B beinhaltet, bleibt die B produktion erhalten,wenn man Pkt 1 u 2 wiederholt. bei diesem bsp ist das nicht der fall, deswegen verschwindet die B produktion! u ich hab gestrn versucht auf dieses problem einzugehen, aber niemand hat sich drum interessiert!! :D
schrankk
05-11-2008, 18:58
also, soweit ich das verstanden habe, werden alle Bs durch diese produktion (B -> A -> ..) ersetzt, deswegen wird im skriptum a die A produktion länger, aber da die A produktion selbst ein B beinhaltet, bleibt die B produktion erhalten,wenn man Pkt 1 u 2 wiederholt. bei diesem bsp ist das nicht der fall, deswegen verschwindet die B produktion! u ich hab gestrn versucht auf dieses problem einzugehen, aber niemand hat sich drum interessiert!! :D
es steht in Folien ausdrücklich, dass "wir B->A durch B->aB|a ersetzen", nicht mehr und nicht weniger... Und wir tun es genau deswegen, da B->A ein Einheitsproduktion darstellt!! Sonst habe ich früher mir selbst ausgedacht (wie vl. du jetzt), dass es alle Symbole B in allen Produktionen ersetzt werden müssen, was eigentlich überhaupt nirgendwo steht!! Und sonst meine Meinung bzgl. Bespiel aus VO kannst du oben finden! ;)
Al Kupone
05-11-2008, 19:09
schon klar, ich weiß was meinst, aber schau dir die folien bzw das bsp im skriptum nochmal an, da wirst sehen, dass das B in der A-produktion ersetzt wird u auch in der S-produktion, somit wurde alle Bs in P ersetzt. u hab gerade was bemerkt: das bsp im skriptum zeigt a eine weitere einheitsproduktion u zwar S -> aA|B ..also S -> B wäre eig a eine..wird aber nicht erwähnt bzw außer acht gelassen..selbst wenn am ende nix bringt, hätten sie es doch erwähnen müssen oder ist es in diesem fall keine einheitsproduktion?
schrankk
05-11-2008, 19:15
schon klar, ich weiß was meinst, aber schau dir die folien bzw das bsp im skriptum nochmal an, da wirst sehen, dass das B in der A-produktion ersetzt wird u auch in der S-produktion, somit wurde alle Bs in P ersetzt. u hab gerade was bemerkt: das bsp im skriptum zeigt a eine weitere einheitsproduktion u zwar S -> aA|B ..also S -> B wäre eig a eine..wird aber nicht erwähnt bzw außer acht gelassen..selbst wenn am ende nix bringt, hätten sie es doch erwähnen müssen oder ist es in diesem fall keine einheitsproduktion?
anscheinend hast du aber wirklich keine Lust, die obere Posts in diesem Thread zu lesen.
http://www.informatik-forum.at/showpost.php?p=543734&postcount=30
http://www.informatik-forum.at/showpost.php?p=543739&postcount=31
http://www.informatik-forum.at/showpost.php?p=543747&postcount=33
viel Spaß :thumb:
Al Kupone
05-11-2008, 19:26
ganz genau, es gibt noch S->B in diesem Beispiel... Also auch eine Einheitsproduktion, auf die (im gegensatz zu B->A) leider nicht aufmerksam gemacht wurde!! :(
Einiges verstehe ich aber immer noch nicht! Das Vorkommnis von B in der Produktion A->aB wird eben auch ersetzt... und von A ausgehend gibt es schon sicher keine Einheitsproduktion A->B!! :o
Edit: hab so bisschen darüber nachdeacht und bin zum für mich beruhigenden Schluß gekommen, dass es einfach ein kleiner Fehler in Skriptum vorgekommen ist, da dieses kleine Ersetzen absolut kein Sinn macht... sonst hab ich ganze Verfahren endlich kapiert!! :cool:
das mit der ersetzung von B in S hab i schon kapiert, aber wie selber schreibst, weißt du selber nicht, warum das B in A ersetzt wird u nimmst an, es ist ein kleiner fehler..wenn es ein fehler wäre, würden die weitern schritten nicht stimmen und die dozentin hätte diese a korrigiert beim präsentieren bzw hätte uns über den fehler erzählt..also im großen und ganzen, weißt a net genau, warum das ersetzt wird.:thumb:
Ist eigentlich eh nicht so schwer, nur Papier verbraucht man viel :D Wen's interessiert - ich komm am Ende auf das hier:
S -> eps | EB
A -> FE | a
B -> CG | FE | DD | a
C -> EB
D -> b
E -> AC
F -> a
G -> CD
12 Produktionen plus Epsilon-Produktion. Wer bietet weniger?
vBulletin® v3.7.1, Copyright ©2000-2009, Jelsoft Enterprises Ltd.