FB18 - Das Forum für Informatik

fb18.de / Bachelorstudieng / PM Formale Informatik

FGI 2 - Blatt 7

FGI 2 - Blatt 7 2007-12-07 13:55
Anonymer lUser
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…

RE: FGI 2 - Blatt 7 2007-12-07 13:57
Anonymer User
PS: Blatt hier: http://www.informatik.uni-hamburg.de/TGI/lehre/vl/WS0708/FGI2/sec/fgi2-a7.pdf

RE: FGI 2 - Blatt 7 2007-12-07 19:23
UncleOwen
[14]

RE: FGI 2 - Blatt 7 2007-12-08 12:27
Anonymer User
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.

RE: FGI 2 - Blatt 7 2007-12-08 12:42
Anonymer User
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 :)

RE: FGI 2 - Blatt 7 2007-12-08 14:49
Anonymer User
Danke für die hervorragende Erklärung, Frank.
Jetzt verstehe ich das endlich!