Hallo

Bei der Bearbeitung von F4 bin ich über eine Aufgabe gestolpert. Die Frage ist, ob P=(x -> P -> y | z -> STOP) als Transitionssystem durch das beschrieben Kalkül (Skript S.18, Def. 2.8) darstellbar ist. Meiner Meinung nach lautet die Antwort nein, aber mir fehlt eine vernünftige Begründung. Wer kann helfen?

Hallo

Bei der Bearbeitung von F4 bin ich über eine Aufgabe gestolpert. Die Frage ist, ob P=(x -> P -> y | z -> STOP) als Transitionssystem durch das beschrieben Kalkül (Skript S.18, Def. 2.8) darstellbar ist. Meiner Meinung nach lautet die Antwort nein, aber mir fehlt eine vernünftige Begründung. Wer kann helfen?

Die Menge aller möglichen Ausführungsfolgen als Formale Sprache über {x,y,z}* betrachten hilft hier weiter:
die kürzeste Ausführungsfolge wäre doch "z", die nächste "xzy" und dann "xxzyy" und …
Was ist das für eine Sprache für den Prozess P ?

hilft das schon??

Na, eine reguläre Sprache x^n z y^n, aber irgendwie fehlt mir da immer noch ein Gedankenschritt. Ich stecke im F2/F3 Stoff leider auch nicht mehr so tief drin.

Na, eine reguläre Sprache x^n z y^n,

Zunächst mal will ich anmerken, dass hier die Bedeutung
von "P=(x -> P -> y | z -> STOP)" garnicht definiert ist,
aber da theorinix nun ausgeholfen hat, kann die Aufgabe
bearbeitet werden.

Du musst nun herausfinden, ob ein Transitionssystem, das
als Ausführungsfolgen die Menge {x^n z y^n | n >= 0}
besitzt, entstehen kann, wenn man die Regeln des Kalküls
anwendet. Also musst du entweder ein Transitionssystem
finden, das obige sprache beschreibt und durch das Kalkül
entsteht, oder du findest eine Begründung, warum kein
Transitionssystem, das beim Kalkül entsteht, diese Sprache
beschreibt. Wenn du hier stecken geblieben bist, guck doch
mal, ob es eine Eigenschaft gibt, die alle im Kalkül
entstehenden Sprachen haben, die aber obige Sprache nicht
hat.

Hast du's jetzt raus?