Moin!
Sehe ich das richtig, dass bei Aufgabe 7.1.1 im Grunde genommen nur ein Graph gefordert wird? Mir faellt nicht ein, wie ich <X|E1> <Y|E1> einzeln malen soll…
Hab ich auch nur einen Graph gezeichnet. Die beiden sind identisch - so habe ich auch hingeschrieben.
Problem:
Bei aufgabe 7.1.2. soll man die Transitionsübergänge beweisen. Um die Übergänge zur Termination zu beweisen, fehlen mir irgendwie die Regeln. Sei z.B. <L|E> eine Lösung der rekursiven Spezifikation E. und c sei der Übergang zur Termination T. D.h. zu zeigen ist:
<L|E> -c-> T
Ich fange mit der Axiom, wie gewöhnt, an. Und nun ? Ich vermute, man benutzt nun die erste Transitionsregel: wenn ti(<X1|E>,…,<Xn|E>)-v->T dann <Xi|E>-v->T. Diese verstehe ich nicht.
Ja, die Regel(n) sind etwas knifflig. Mal gucken ob ich die erklären kann :)
Sagen wir mal du hast eine Spezifikation mit drei Variablen:
(Welche ist jetzt eigentlich egal, ich will das nur kurz veranschaulichen)
X_1 = a*X_2 + b*X_3 + c
X_2 = X_1*c
X_3 = a*X_2 + d
(Oft hast du statt X_2 und X_3 sowas wie Y und Z, aber das ist egal, gell?)
Die rechte Seite einer dieser Gleichungen - allgemein der i-ten Gleichung - kannst
du nun als einen 'Term abhängig von den Variablen X_1, X_2 und X_3' verstehen.
Dafür schreibt man t_i(X_1, X_2, X_3). Bspw. ist t_2(X_1,X_2,X_3) also einfach
die rechte Seite der obigen Gleichung für X_2, d.h. X_1*c.
Mit <X_i|E> wird die "Lösung von X_i bzgl. der Spezifikation E" bezeichnet.
t_i(<X_1|E>,…,<X_3|E>) ist also wie oben der Term auf der rechten Seite der
i-ten Gleichung. Diesmal aber schreibst du überall wo X_1 steht <X_1|E> hin etc.
(also kannst du t_i( …. ) auch als eine Funktion mit (hier) drei Argumenten verstehen).
Man beachte, dass nicht immer alle Argumente auch in dem Term auftreten müssen!
Wie oben ist ja z.B. t_2(X_1, X_2, X_3) = X_1 * c (X_2 und X_3 werden also gar nicht
benutzt).
So, nun letztendlich zu der Regel: Die Regel besagt: Wenn du
t_i(<X_1|E>, <X_2|E>, <X_3|E>) – v –> y
abgeleitet hast (für ein i), d.h. weiter in obigem Beispiel für i = 2, wenn du
<X_1|E> * c – v –> y
abgeleitet hast (wobei y irgendein Prozessterm ist), dann darfst du dafür auch
einfach
<X_2|E> – v –> y
schreiben. Warum? Naja, <X_1|E> * c ist ja gerade die rechte Seite der Gleichung
für X_2, wobei du statt X_1 dort die *Lösung* für X_1 (in E) hingeschrieben hast. In
der Gleichung ergibt sich dann auf der linken Seite auch die Lösung für X_2 (vergleiche
mit linearen Gleichungssystemen! Wenn ich so etwas wie y = x + 3 habe und ich weiss
die Lösung für x ist z.B. 5, dann kann ich die Lösung für y (nämlich 8) ausrechnen). Die
Lösung für X_2 wird nun gerade (bzgl. E) notiert durch <X_2|E>.
Alles klar? (Die andere Regel ist ähnlich, nur dass da statt y halt das Terminationssymbol
steht.)
Kurz zusammengefasst: Wenn du x – v –> y abgeleitet hast und x ist gerade der
Prozessterm, der der rechten Seite der i-ten Gleichung deiner Spezifikation entspricht
(wobei auf dieser rechten Seite statt den Variablen X_1, X_2 etc. überall deren Lösung
<X_1|E> usw. steht), dann darfst du statt x einfach die Lösung der i-ten Variablen
schreiben, also <X_i|E>.
Noch kürzer: Du ersetzt die i-te Gleichung durch die Lösung der i-ten Variablen (wobei
in der i-ten Gleichung überall <X_1|E> etc. stehen müssen).
Hoff' es hilft!
Frank :)
Danke für die hervorragende Erklärung, Frank.
Jetzt verstehe ich das endlich!