
Test Generation
q
1
q
3
q
2
q
4
q
5
a/0
a/0
a/0
a/1
b/1
b/1b/1
b/1 b/1
a/1
Fig. 3.13 The transition and output functions of a simple FSM.
3.5 CHARACTERIZATION SET
Most methods for generating tests from FSMs make use of an important
set known as the characterization set. This set is usually denoted by W
and is sometimes referred to as the W-set. In this section, we explain how
one can derive a W-set given the description of an FSM. Let us examine
the definition of the W-set.
Let M = (X, Y, Q, q
1
, ‰, O) be an FSM that is minimal and com-
plete. A characterization set for M, denoted as W, is a finite set of input
sequences that distinguish the behavior of any pair of states ...