[SOLVED] CS Prof. Dr.-Ing. Jo rg Raisch

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),andwehave2x0 =2=1=2x.
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),but30 =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