For each petri net if a deadlock or overflow occur write the

For each petri net, if a deadlock or overflow occur, write the sequence of markings and transitions leading up to it.

Figure 3 First Petri Net Figure 4 Second Petri Net

Solution

A petrinet is a tuple <P,T where P is the set of places, T is the set of transitions.Each transition T is a tuple < I,O> where I is a function t consumes I(p) tokens in each place p. O is a function t produces O(p) tokens in each place p.

Markings:

• The distribution of the tokens in the places is formalised by the notion of marking,

which can be seen:

• either as a function m, s.t. m(p) is the number of tokens in place p • or as a vector m=m1, m2,... mnwhere mi is the number of tokens in place pi.

Figure3: Markings are

m =1,0,1 m = p1, p3m(p1)=1, m(p2)=0, m(p3)=1.

Figure4: Markings are

m =1,0,0 m = p1,m(p1)=1, m(p2)=0, m(p3)=0.

Transitions:

• A transition t = I,Ocan be fired from m iff for any place p: m(p) I(p)

• The firing transforms the marking m into a marking m for any place p: m’(p) = m(p) - I(p) + O(p).

Figure3:

I(t1)={p1}, I(t2)={p2}, I(t3)= {p3},I(t4)={p2,p3}.

O(t1)={p2},O(t2)={p3},O(t3)={p1},O(t4)={p1}.

Figure4:

I(t1)={p1}, I(t2)={p1}, I(t3)= {p2},I(t4)={p3} I(t5)={p3}.

O(t1)={p2},O(t2)={p3},O(t3)={p3},O(t4)={p2 O(t5)={p2,p3}.