Chow's Method is a method for testing FSMs. It uses the following to define a set of tests:

VW U VXW

Here, V is a minimal state cover. A state cover is a set of input sequences which allow each state to be reached from the start state. A minimal state cover is where each state can only be reached using a single input sequence from the state cover set i.e. even though there may be many ways to reach a state, only one way (the shortest) is used in V.

W is a characterising set. See State-Based Testing / Verification for more information on characterising sets. The combination of V and W therefore enables all the states in an FSM to be tested.

X is a set of input values to be tested from each state. These input values trigger transitions which are then tested for. The combination of V, X and W enables all transitions from all states to be tested. The values in W are used to check whether the transitions led to the correct state.

The use of VW U VXW therefore allows for complete testing of an FSM. Duplicate input sequences can be removed from the resultant set of input sequences. When testing the system, the set of input sequences are separated by resets. Chow's method therefore requires a reliable reset operation. Chow's method will always work as long as the number of actual states in the Implementation Under Test (IUT) is no more than in the correct FSM which the IUT is based on.

Search for "Chow's Method" on: Google | Kelkoo | Amazon | eBay (UK) | eBay (US)

Search for "Chow's Method" on the rest of Computing Students: Chow's Method