FB18 - Das Forum für Informatik

fb18.de / Diplom Informatik / Theoretische Informatik (HS)

Prozessalgebra: Rekursion

Prozessalgebra: Rekursion 2007-09-13 22:30
Morpheus
Ich habe da eine Aufgabe in dem Buch "Introduction to process algebra" von Wan Fokkink (Woraus auch Herr Falk sein Kapitel über Prozessalgebra gemacht hat), eine Aufgabe die ich nicht ganz verstehe:
Bitte aus folgendem Prozessterm den Prozessgraphen ableiten:
<X|X=YX, Y=bY>Die Lösung laut dem Buch lautet:
<X|X=YX, Y=bY> ->(b) <Y|X=YX, Y=bY><X|X=YX, Y=bY>(das b soll hier natürlich eingentlich über den Pfeil)
Wie kommt es zu einer Lösung mit zwei Prozesstermen?

Wie immer bedanke ich mich schonmal im vorraus.

RE: Prozessalgebra: Rekursion 2007-09-14 17:57
georg
Wie kommt es zu einer Lösung mit zwei Prozesstermen?

Du meinst, wie obige Lösung zustande kommt?
Dafür muss man die Transitionsregeln für die Rekursion
anwenden (im aktuellen Skript S. 156):

Zunächst gilt aufgrund der Regeln in 4.3:
b<Y| X=YX, Y=bY> ->(b) <Y| X=YX, Y=bY>und damit wegen der Transitionsregel für Rekursion
<Y| X=YX, Y=bY> ->(b) <Y| X=YX, Y=bY>also wieder mit den Regeln in 4.3
<Y| X=YX, Y=bY><X| X=YX, Y=bY> ->(b) <Y| X=YX, Y=bY><X| X=YX, Y=bY>was mit der Transitionsregel für Rekursion wiederum ergibt
<X| X=YX, Y=bY> ->(b) <Y| X=YX, Y=bY><X| X=YX, Y=bY>
Insbesondere müsste vom zweiten Term in der obigen Lösung noch eine mit b
beschriftete Kante auf den Term selber gehen.

Bei den Rekursionen muss man immer die rechte Seite der Gleichung
verwenden, um damit Kanten zu inferieren und anschließend diese auf den
rekursiven Ausdruck anwenden. Soweit klar geworden?

PS: Latex geht mal wieder nicht! [8]