Prof. Dr.-Ing. Jo ̈rg Raisch
Germano Schafaschek
Soraia Moradi
Behrang Nejad
Fachgebiet Regelungssysteme
Fakulta ̈t IV Elektrotechnik und Informatik Technische Universita ̈t Berlin Lehrveranstaltung ”Ereignisdiskrete Systeme“ Wintersemester 2019/2020
Exercise 2 — Solution
Exercise 2.1
a. Unbounded;
not reversible; persistent;
t1, t3, t4 live; t2 dead.
b. Unbounded; reversible; persistent;
t1,t2,t3,t4 live.
c. Bounded; reversible;
not persistent;
t1, t2, t3, t4 live; t5 dead.
d. Bounded;
not reversible;
not persistent;
t1, t3 L3-live; t2, t4 L1-live.
e. Bounded; reversible; persistent;
t1,t2,t3,t4 live.
f. Unbounded; not reversible; persistent; t1,t2,t3,t4 live.
Exercise 2.2
a.
−1 0 −1 A=1 0 0 1 1 − 1
0 1 −1
No, based solely on the incidence matrix it is not possible to exactly determine the presence or the weight of arcs in the Petri net graph. For instance, based on A it is not possible to know that, in this Petri net, there are arcs between p2 and t2 or the weight of arcs between p3 and t2.
1
b. The coverability tree is shown below.
t3
1 t2 1
1 ω
1 ω
0
0 t2 1
1
ω
ω ωω
t1
2 1
0
0 t1
t2
1
0 1 t1 0 ω
ωω
00ω 2
2 t2 0 0
2
0 2t22 ω ω
ωω
c. Unbounded; not reversible; not persistent; t1, t3 L1-live; t2 live.
d. No, the petri net is not blocking because at the initial marking t1 can fire, and in any subsequent
reachable state t2 can always fire.
e. Not conservative with respect to γ1: the marking x ̄ = [1 1 2 1]′ is reachable (by firing t1 → t2 from the initial marking), and we have γ1′ x0 = 2 ̸= 3 = γ1′ x ̄.
Not conservative with respect to γ2: the marking xˆ = [0 1 1 0]′ is reachable (by firing t1 → t2 →t3 fromtheinitialmarking),andwehaveγ2′x0 =2̸=1=γ2′xˆ.
1 0 0 0
0 1 0 ω
0 0
ω
1 ω
0
ω
Exercise 2.3
a. The coverability tree is shown below.
1
0 t1
0 0
b. ξ1, ξ4 reachable; ξ2, ξ3 not reachable. c. t1 −t3 −t2 −t4 −t4.
0 0
1 0
1
ω t3,t5
t2
0 t2 ω
0 ω ω 1 0 1
ω ω t4,t5 ω t30 1
0ωω 0 ω
1 t1 00ω
0 000ω
t3 0 t2
t4 1 t1
1 0 ω ω
0ω
2
d. Not conservative with respect to γ1 (it is possible to decide based on the coverability tree; the necessary condition is violated, since there exists a node xk in the tree such that xk5 = ω, but γ15 ̸=0 —seelecturenotes,page27).
Conservative with respect to γ2 (again it is possible to decide based on the coverability tree; in this case the necessary condition is fulfilled and, additionally, γ2xk = 1 for all nodes xk in the tree). Not conservative with respect to γ3 (not possible to decide based on the coverability tree, since γ3 ∈/ Nn0 ; the result can be checked by direct inspection of the Petri net: x ̄ = [1 1 0 1 0]′ ∈ R(N,x0),butγ3×0 =0̸=1=γ3x ̄).
Exercise 2.4
a. t1 , t5 L1-live; t2 , t4 L3-live; t3 dead;
b. The coverability tree is shown below.
t6 live.
0
1 0 1 0
0 0
1 1
0 0
t4
t5 0
1 0
1
0 0
0 t6 0
0
1 0 0 t1 1
t2
0 0
0 1
t5
00
1 0
t2
1 0
1 0
0 111
t6
0
1 0
0 1
c. Yes, the symbol ω does not appear anywhere in the coverability tree.
d. Conservative with respect to γ1, γ2; not conservative with respect to γ3.
In this case all three answers can be based on the coverability tree, since we have γi ∈ N50 for all i ∈ {1,2,3}; there is no ω in any node of the tree; and for any node xk in the tree it holds that γ1′ xk = 1 and γ2′ xk = 1 (both constant), whereas there exist nodes xp , xq , xr for which γ3′ xp = 1, γ3′ xq = 0, and γ3′ xr = 2 (not constant) — see page 27 of the Lecture Notes.
e. t1 , t3 , t5 L1-live; t2 , t4 L3-live; t6 live.
The Petri net is bounded (again the symbol ω does not appear anywhere in the coverability tree). Not conservative with respect to γ1, γ2, γ3.
f. x0 = [0 1 1 0 0]′. For this initial state, the Petri net is blocking.
3