Foundations of Software Testing: Fundamental Algorithms and Techniques

Test Generation from Finite-State Models

2. Repeat the steps (a) through (d) given below for each pair of states

(q

i

, q

j

), i = j,inM.

(a) Find r, 1 ≤ r < n such that the states in pair (q

i

, q

j

) belong to

the same group in P

r

but not in P

r+1

. In other words, P

r

is the

last of the P tables in which (q

i

, q

j

) belongs to the same group.

If such an r is found then move to Step (b), otherwise we find

an Á ∈ X such that O(q

i

, Á) = O(q

j

, Á), set W = W ∪{Á}, and

continue with the next available pair of states.

The length of the minimal distinguishing sequence for (q

i

, q

j

)

is r + 1. We denote this sequence as z = x

0

x

1

...x

r

,wherex

i

∈

X for 0 ≤ i ≤ r.

(b) Initialize z = Â. Let p

1

= q

i

and p

2

= q

j

be the current pair

of states. Execute steps (i) through (iii) given below ...