Section 9.3 Finite-State Machines
741
Definition PArtition rEfinEMEnt
Given two partitions p 1 and p 2 of a set S, p 1 is a refinement of p 2 if each block
of p 1 is a subset of a block of p 2 .
example 35
Consider again the machine M of Example 34. We know the 0-equivalent states.
To find 1-equivalent states, we look for 0-equivalent states with 0-equivalent next
states. For example, the states 3 and 4 are 0-equivalent; under the input symbol
0, they proceed to states 1 and 6, respectively, which are 0-equivalent states, and
under the input symbol 1 they both proceed to 5, which of course is 0-equivalent
to itself. Therefore, states 3 and 4 are 1-equivalent. Similarly, states 1 and 3 are
1-equivalent and states 4 and 6 are 1-equivalent. Therefore the class 51, 3, 4, 66 of
1-equivalent states is unchanged from the class of 0-equivalent states. But states
0 and 5, themselves 0-equivalent, proceed under the input symbol 1 to states 3
and 0, respectively, which are not 0-equivalent states. So states 0 and 5 are not
1- equivalent; the input string 1 will produce an output string of 01 from state 0
and of 00 from state 5. States 0 and 2 are 1-equivalent. Therefore the l-equivalence
classes for M are
50, 26, 556, 51, 3, 4, 66
To find 2-equivalent states, we look for 1-equivalent states with 1-equivalent
next states. States 1 and 3, although 1-equivalent, proceed under input 1 to states
2 and 5, respectively, which are not 1-equivalent states. Therefore, states 1 and
3 are not 2-equivalent. The states 0 and 2, 1 and 6, and 3 and 4, respectively, are
2-equivalent. The 2-equivalence classes for M are
50, 26, 556, 51, 66, 53, 46
The 3-equivalence classes for M are the same as the 2-equivalence classes.
In Example 35 each successive partition of the states of M into equivalence classes is a refinement of the previous partition. This refinement will always happen; k-equivalent states must also be (k − 1)-equivalent, so the blocks
of the (k − 1)-partition can only be further subdivided. However, the subdivision process cannot continue indefinitely (at worst it can go on only until each
partition block contains only one state); there will eventually be a point where
(k − 1)-equivalent states and k-equivalent states coincide. (In Example 35,
2-equivalent and 3-equivalent states coincide.) Once this happens, all next states for
members of a partition block under any input symbol fall within a partition block.
Thus, k-equivalent states are also (k + 1)-equivalent and (k + 2)-equivalent,
and so on. Indeed, these states are equivalent.
The total procedure for finding equivalent states is to start with 0-equivalent
states, then l-equivalent states, and so on, until the partition no longer subdivides.
A pseudocode description of this algorithm is given. It isn’t nearly as complex as
it looks, but it does involve checking many pairs of states, just as in Example 35.
741
Definition PArtition rEfinEMEnt
Given two partitions p 1 and p 2 of a set S, p 1 is a refinement of p 2 if each block
of p 1 is a subset of a block of p 2 .
example 35
Consider again the machine M of Example 34. We know the 0-equivalent states.
To find 1-equivalent states, we look for 0-equivalent states with 0-equivalent next
states. For example, the states 3 and 4 are 0-equivalent; under the input symbol
0, they proceed to states 1 and 6, respectively, which are 0-equivalent states, and
under the input symbol 1 they both proceed to 5, which of course is 0-equivalent
to itself. Therefore, states 3 and 4 are 1-equivalent. Similarly, states 1 and 3 are
1-equivalent and states 4 and 6 are 1-equivalent. Therefore the class 51, 3, 4, 66 of
1-equivalent states is unchanged from the class of 0-equivalent states. But states
0 and 5, themselves 0-equivalent, proceed under the input symbol 1 to states 3
and 0, respectively, which are not 0-equivalent states. So states 0 and 5 are not
1- equivalent; the input string 1 will produce an output string of 01 from state 0
and of 00 from state 5. States 0 and 2 are 1-equivalent. Therefore the l-equivalence
classes for M are
50, 26, 556, 51, 3, 4, 66
To find 2-equivalent states, we look for 1-equivalent states with 1-equivalent
next states. States 1 and 3, although 1-equivalent, proceed under input 1 to states
2 and 5, respectively, which are not 1-equivalent states. Therefore, states 1 and
3 are not 2-equivalent. The states 0 and 2, 1 and 6, and 3 and 4, respectively, are
2-equivalent. The 2-equivalence classes for M are
50, 26, 556, 51, 66, 53, 46
The 3-equivalence classes for M are the same as the 2-equivalence classes.
In Example 35 each successive partition of the states of M into equivalence classes is a refinement of the previous partition. This refinement will always happen; k-equivalent states must also be (k − 1)-equivalent, so the blocks
of the (k − 1)-partition can only be further subdivided. However, the subdivision process cannot continue indefinitely (at worst it can go on only until each
partition block contains only one state); there will eventually be a point where
(k − 1)-equivalent states and k-equivalent states coincide. (In Example 35,
2-equivalent and 3-equivalent states coincide.) Once this happens, all next states for
members of a partition block under any input symbol fall within a partition block.
Thus, k-equivalent states are also (k + 1)-equivalent and (k + 2)-equivalent,
and so on. Indeed, these states are equivalent.
The total procedure for finding equivalent states is to start with 0-equivalent
states, then l-equivalent states, and so on, until the partition no longer subdivides.
A pseudocode description of this algorithm is given. It isn’t nearly as complex as
it looks, but it does involve checking many pairs of states, just as in Example 35.