Übung 7 - Informatik 12

Informatik 12
Cauerstraße 11
91058 Erlangen
TECHNISCHE FAKULTÄT
7. Übung zur Vorlesung Ereignisgesteuerte Systeme
Die nächste Übung findet als praktische
Übung im Raum 02.133 statt!
Aufgabe 1 Betrachten Sie das folgende Petri-Netz mit Anfangszustand M0 = [1, 1, 0, 0]. Berechnen
Sie den Ereichbarkeitsgraphen und verwenden Sie diesen, um zu zeigen, dass der Zustand [0, 0, 0, 0]
nicht erreichbar ist.
p1
p2
t1
p3
t2
p4
t3
Aufgabe 2 Petri-Netze eignen sich auch, um Datenfluss zu beschreiben. Transitionen repräsentieren
hierbei Operationen und Stellen die Speicherung von Daten.
Zeichnen Sie ein Petri-Netz, das die Gleichung R = (X +Y )∗(X −Z)+((X ∗Y )/(X −Y )) modelliert.
Achten Sie darauf, dass keine ungültigen Operationen stattfinden können.
Aufgabe 3 Unter Orangen-Saft verstehen wir im Folgenden die Flüssigkeit, die aus Orangen durch
Pressen erzeugt wird. Orangen-Nektar ist Orangen-Saft, der mit Wasser im Verhältnis 1 : 1 verdünnt
wurde.
Das folgende Petri-Netz modelliert eine Produktionsanlage zur Herstellung von 1-`-Packungen mit
Orangen-Saft und mit Orangen-Nektar:
1
Erläuterungen zum Netz:
p1
• Eine Marke in p2 entspricht 12 `
Wasser. Wasser steht ohne Einschränkung zur Verfügung; dies
wird durch die Konstruktion p1
und t1 simuliert.
p3
Orangen
t1
10
t2
Presse
• Ein Token in p3 entspricht einer
Orange.
p4
Orangen−Saft−Behälter
• Die Presse t2 erzeugt aus 10
Orangen 12 ` Orangen-Saft und
leitet ihn in den Orangen-SaftBehälter p4.
p2
Wasser
2
t3
Mixer
p5
Orangen−
Nektar−
Packungen
t4
Abfüll−
maschine
p6
Orangen−
Saft−
Packungen
2
• Der Mixer t3 mischt 12 ` Wasser und 12 ` Orangen-Saft zu 1`
Orangen-Nektar und füllt ihn in
eine 1-`-Packung ab.
• Die Abfüllmaschine t4 füllt 1`
Orangen-Saft in eine 1-`-Packung
ab.
a) Stellen Sie die Inzidenzmatrix A des Petri-Netzes auf. Orientieren Sie sich dabei an der Nummerierung der Stellen und Transitionen.
b) Entscheiden Sie unter Verwendung der Inzidenzmatrix A, ob M1 = (1, 0, 0, 0, 8, 6) von der
Anfangsmarkierung M0 = (1, 0, 200, 0, 0, 0) aus erreichbar ist. Was bedeutet das?
c) Stellen Sie den Erreichbarkeitsgraphen für die Anfangsmarkierung M00 = (1, 0, 10, 0, 0, 0) auf
und beantworten Sie anhand des Graphen folgende Fragen: Ist das Netz deadlockfrei? Ist bei
Anfangsmarkierung M00 die Produktion einer 1-`-Packung Orangen-Saft möglich?
d) Entscheiden Sie anhand der Transitionsinvarianten, ob das Netz reversibel ist.
e) Die Stelleninvariante des gegebenen Netzes ist IST = (a, 0, b, 10b, 10b, 20b). Was folgt daraus
für die einzelnen Stellen?
f) Es stehen 200 Orangen zur Verfügung, und es sollen genau neun 1-`-Packungen OrangenNektar hergestellt werden. Berechnen Sie unter Zuhilfenahme der Inzidenzmatrix A, wie viele
1-`-Packungen Orangen-Saft maximal produziert werden können.
g) Angenommen, die Kapazität des Orangen-Saft-Behälters p4 ist durch 2` beschränkt. Das heißt,
die Stelle p4 hat eine Kapazitätsbeschränkung von K = 4. Formen Sie dieses kapazitätsbeschränkte Petri-Netz in ein äquivalentes Petri-Netz ohne kapazitätsbeschränkte Stellen um.
Aufgabe 4 (Hausübung) Ein Petri-Netz ohne geschlossene Schleifen heißt azyklisch. Für diese Netzklasse gilt folgender Zusammenhang: Ein Zustand M ist genau dann erreichbar vom Anfangszustand
M0 , falls die Gleichung M = M0 + A ·U eine nichtnegative Lösung U hat, wobei A die Inzidenzmatrix
des betrachteten Netzes ist.
a) Zeigen Sie für das folgende Petri-Netz, dass M = [0, 0, 1, 2] erreichbar ist von M0 = [3, 1, 0, 0]
P = {p1 , p2 , p3 , p4 }
T = {t1 ,t2 }
K = {(p1 ,t1 ), (p2 ,t2 ), (p3 ,t2 ), (t1 , p2 ), (t1 , p3 ), (t2 , p4 )}
mit Kantengewichten w(p2 ,t2 ) = 2 und w(p,t) = 1 sonst.
b) Geben Sie eine plausible Interpretation von U.
3

Download Report