CIS 3051 Information Systems Engineering

 



“———————————————————————————————————————————————
Support this Page: http://amzn.to/2kgnzrf
———————————————————————————————————————————————

CIS 3051 Information Systems Engineering

Naudi

 

40% assignment

60% Exam

 

Petri Nets models IS
Flow graph for Quality Assurance
Maintenance productivity

Petri net

 

 

e.g:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

In this example T3 has no input, so it always enabled which means it can always fire.

 

Reachability Graphs

 

 

P1 P2 P3

M0 = (0, 0, 0)

t3 (t3 fires)

t3*
M1 = (1, 0, 0)

t1

 

 

M2 = (0, 1, 0)

t3
M3 = (1, 1, 0)

*t3 fires again

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

P1 P2 P3

M0 = (0, 0, 1)

t3

t2

t3
M1=(1,0,1) (0, 0, 0)

 

 

M2=(0,1,1)(1, 0, 0)t3

t3 t1 t1

t3
M3 = (1, 1, 1) (0, 1, 0)

 

t3

 

(1, 1, 0)

 

 

 

 

 

 

 

 

 

 

Real Life Example – road passing over a railway with bridge opening and closing when a train passes by.

 
Oval: 1

Train

 

Oval: 3Oval: 2Gate one way

 

 

 

 

 

 

 

 

The gate can be in these 4 situations:

1. Gate Open

2. Gate Open to Close

3. Gate Closed

4. Gate Closed to Open

 

The train can be in these situations

Tran Away (1)
Train passing by (2)
Train Leaving (3)

If we want a transition that will not fire if 2 places are marked we draw a dotted line which is known as the inhibitor arc.

 

P2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Without the inhibitor arc t1 is enabled, the inhibitor disables t1 (if P3 is marked). If only P1 is enabled t1 can fire.

 

 

 

Gate Open

Gate Train

Train far away

Gate Open to Close

Gate Closed

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

If we draw one Petri Net for this situation we will have this diagram:

 

Train Gate

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Train passing

 

 

 

 

 

 

 

Train away

 

 

 

 

 

 

 

 

 

 

In our case we are drawing safe Petri nets. Safe Petri nets in each place can have a maximum of one dot only. If it is not a safe Petri net then there is no limit of dots per place. The problem with non safe Petri nets is that if you want to fire the first dot and there are a number of dots it is impossible to recognise the first one. Therefore coloured Petri nets are used.

 

 

There are 3 simple steps to know

Workings of a Petri net
Draw a Petri net
Draw a reach-ability graph

E.g. 8.1:

 

Producer A Producer B

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Consumer 1 can buy either from A or from B since there is no priority. If there is a preference if you can buy from A and not from B then the diagram would be like 8.2

 

E.g. 8.2: Petri Net

 

Producer A Producer B

 

t0 t2

 

 

P0P1

 

 

t1 t3

 
P2

 

 

Reachability Graph

 

P0, P1, P2

(0, 0, 0)

t0t2

t0

(1, 0, 0) (0, 1, 0)

t1t2

 

(0, 0, 1)(1, 1, 0)

t1

t0t2

t0

(1, 0, 1) (0, 1, 1)

t2t1

t0

t2 (1, 1, 1)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Flow Graphs (Control Flow Graphs — CFG)

 

Aim:

P

Flow Graph

 

Cyclomatic Statementbranch coveragepath

Complexity

 
State

 

 

Directed line

 

3 rules that govern a good flow graph (a CFG is valid if)

1. There is one start and one end node (State).

2. For each node there are a maximum of 2 outgoing arrows.

3. For each node N in the CFG there exists at least one path from the start node to N and at least one path from N to the end node.

 

 

 

 

 

 

 

 

 

a. x

 

 

x

 

 

 

 

R

 

E.g. 1:

s1

if s2 than s3

else s4

s5

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

E.g. 2:

s1

if s2 then s3

s5

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

E.g. 3:

s1

repeat s2

until s3

s4

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

e.g. 4:

s1

for (s2, s3, s4)

s5

endfor

s6

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

E.g. 5

s1

if s2 and s3 than s4

else s5

s6

 

 

 

 

 

 

 

 

 

F T

 

F

 

 

T

 

 

 

 

E.g. 6:

s1

if s2 or s3 then s4

else s5

s6

 

 

 

 

 

 

 

TF

 

 

 

T

 

 

 

 

 

 

 

 

 

 

E.g. 7:

s1

case s2 of

s3: s31 break

s4: s41 break

s5: s51 break

else s6

end case

s7

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Cyclomatic Complexity

 

How to know that the CFG is valid?

To know that a CFG is valid Cyclomatic complexity is used. There are 3 ways to do this:

D + 1 Ã total decisions + 1
#(regions) Ã number of regions
E – N + 2 à total edges (arrows) — total nodes (State) + 2

A decision is a state with 2 directed lines (arrows), and a node is a state (circle).