Hallo zusammen,

ich lerne gerade fuer meine demnächst anstehende PNL Pruefung
und habe da einmal eine Frage zu Ableitungen von Prozessgraphen
zu rekursiven Spezifikationen und hoffe dass mir da vielleicht einer von euch weiterhelfen kann.

Mir ist nicht ganz klar, wie ich die Ableitung von z.B.
aXb+c korrekt aufschreibe. Zwar ist mir klar, dass der
korrekte Prozessgraph wohl wie folgt aussieht.

a a aXb+c----aXbb+c------aXbbb+c... | | . |c |c . | | .
Nun frage ich mich, wie ich die formal wie im Beispiel 2.29
im Skript mit Angabe der einzelnen Schritte und angewandten
Transitionsregeln aufschreibe ?

Hier mein bisheriger Versuch: (# soll Termination bedeuten)

a a-># ------ a a-># v a x-># aXb->aXb ------ mit x=a, y=Xb, v=a v x*y->y v a y-># aXb+c->Xb+c ------ mit x=aXb, y=c, v=a v x+y-># v a t1(X)->y X->Xb+c -------- mit t1(X)=aXb+c,y=Xb+c v X->y
So und nun weiss ich nicht wirklich weiter. Wie komme ich jetzt auf
Xbb, Xbbb usw. ?

Wie komme ich jetzt auf Xbb, Xbbb usw. ?

Indem Du das ganze nochmal machst. Mit dem Transitionskalkül (hat das 'nen richtigen Namen?) kannst Du immer nur eine Transition ableiten.

Leider verstehe ich das immer noch nicht so recht.
Wie wuerde das dann konkret weitergehen ? Etwa so ?

a aX->a(Xb+c) a aXb->a(Xb+c)b a aXb+c->a(Xb+c)b+c a X->a(Xb+c)b+c
Das ist doch irgendwie nicht die richtige Loesung.
Also wie geht das dann ? Waere nett wenn du vielleicht
ein paar Schritte darstellen koenntest.

Und wie ausfuehrlich (viele Schritte) muss man das
eigentlich in der Pruefung zeigen ?

wenn du so genau fragst dann fallen mir jetzt doch die Fehler im vorherigen Post auf,

[quote] v a y-># aXb+c->Xb+c ------ mit x=aXb, y=c, v=a v x+y-># [/quote] ist ein total falscher Schritt, da c ja mit a gar nicht terminiert (die Prämisse in der Regelanwedung) und als Ergebnis dieser Regelanwendung auf der rechten Seite # stehen müsste korrekter sieht die Anwendung dieser Regel z.B so aus: v c y-># aXb+c-># ------ mit x=aXb, y=c, v=c v x+y-># ------------ [quote] a X->Xb+c [/quote] ist letztendlich nicht korrekt, dein Prozessgraph leider auch nicht, zum Prozessgraph kannst du die Lösung hier nachschauen [url=http://3773.rapidforum.com/topic=107581874256]http://3773.rapidforum.com/topic=107581874256[/url] wenn ich mich nicht irre steht in anderen Topics eventuell auch was dazu, ich meine ich hätte auch irgendwann mal den falschen Prozessgraphen gepostet ;) edit ah, der andere Thread ist da ja auch gelinkt: [url=http://3773.rapidforum.com/topic=107582295597]http://3773.rapidforum.com/topic=107582295597[/url] (und dort stehen sogar mehrere falsche Versionen des Prozessgraphen drin ;) ) zum Ableiten hat wohl noch keiner was aufgeschreiben

Zunaechst schon einmal vielen Dank fuer deine Hilfe.

Also der korrekte Prozessgraph sieht dann wohl so aus.
Das ist mir jetzt auch klar.

a a aXb+c----(aXb+c)b------(aXb+c)bb... | | . |c |c .c | | .b # |b .b # ..
Nun habe ich mich noch einmal an der Ableitung versucht:

a (1) a-># ------ a a-># v a x-># (2) aXb->Xb ------ mit x=a, y=Xb, v=a v x*y->y v a y->y' (3) aXb+c->Xb ------ mit x=aXb, y=aXb, v=a v x+y->y' v a t1(X)->y (4) X->Xb -------- mit t1(X)=aXb+c,y=Xb v X->y Habe ich damit jetzt schon gezeigt das immer a Xb^n -> Xb^(n+1) Aus (2) folgt dann ja auch: v c y-># aXb+c-># ------ mit x=aXb, y=c, v=c v x+y-># v c t1(X)-># X-># -------- mit t1(X)=aXb+c, v=c v X-># Kann ich da jetzt einfach sagen: c Xb^n -> b^n
Ist das jetzt die richtige und in der Pruefung u.U. geforderte Ableitung ? Oder was muesste in der Pruefung noch kommen ?

klingt schon alles deutlich besser

[quote] v a y->y' (3) aXb+c->Xb ------ mit x=aXb, y=aXb, v=a v x+y->y' [/quote] hier lohnt es sich durchaus korrekt zu bleiben, also: v a y->y' (3) aXb+c->Xb ------ mit x=c, y=aXb, y'=Xb, v=a v x+y->y' [quote] Habe ich damit jetzt schon gezeigt das immer a Xb^n -> Xb^(n+1) [/quote] das kann man nicht so über einen Haufen werfen, aber der entscheidene Teil dafür ist natürlich schon gemacht nun müsstest du (meiner Meinung nach) für jedes n eine einzelne Ableitung machen, also für gegebenes n siehts so aus: v a x->x' (1) X b^n->Xb b^n ------ mit x=X, x'=Xb, y=b^n, v=a v x y ->x' y also ein Schritt aus dem vorherigen (4), ist für beliebiges n gleich [quote] Kann ich da jetzt einfach sagen: c Xb^n -> b^n [/quote] ähnlich wie oben müsste man für jedes n eine einzelne Ableitung machen, die alle gleich aussehen bis auf n eben, auf jeden Fall muss man das ableiten, das fällt nicht vom Himmel (kann man aber durchaus als trivial betrachten) [quote] Ist das jetzt die richtige und in der Pruefung u.U. geforderte Ableitung ? Oder was muesste in der Pruefung noch kommen ? [/quote] richtig, ja (denke ich zumindest), mehr kann man zu einer solchen Aufgabe nicht sagen (denke ich zumindest) gefordert sein dürfte im wesentlichen nur (1) bis (4), aber der Rest ist auch nicht schlecht zu wissen bzw. sollte man ja im Grunde in der Prüfung können ;)