State Partition Method for State Minimization

State Partition Method for State Minimization is also powerful as the Implication Chart Method and better than Row Equivalence method. In this technique, the states are partitioned into groups based on the possibility that they can be combined. Lets consider the example state table as shown in Table 1 for state minimization using state partition method. This method also perform state minimization after some passes. These passes are described below.

Start :- In the first pass there is only one group and this is $P = (S_0S_1S_2S_3S_4S_5S_6)$ .

First Pass :- In the first pass, the states which have different outputs are partitioned in separate groups. Here, $S_0$ , $S_1$ and $S_3$ have same output and thus grouped in $P_1 = (S_0S_1S_3)$ . The rest of the states have same output and thus they grouped as $P_2 = (S_2S_4S_5S_6)$ .

Second Pass :- In this pass, the states are partitioned based upon their $k$ -successors. In order to combine two states, their $k$ -successors should be in the same partition or group.

Consider the first partition $P_1$ and their $k$ -successors are

$0$ -successors – $S_0 \rightarrow S_1$ , $S_1 \rightarrow S_3$ and $S_3 \rightarrow S_1$ . Here, $S_1$ and $S_3$ belong to the same group $P_1$ . States $S_0$ , $S_1$ and $S_3$ can be combined.
$1$ -successors – $S_0 \rightarrow S_2$ , $S_1 \rightarrow S_5$ and $S_3 \rightarrow S_6$ . Here, $S_2$ , $S_5$ and $S_6$ belong to the same group $P_2$ . States $S_0$ , $S_1$ and $S_3$ can be combined.

Now consider the second partition $P_2$ and their $k$ -successors are

$0$ -successors – $S_2 \rightarrow S_5$ , $S_4 \rightarrow S_5$ , $S_5 \rightarrow S_4$ and $S_6 \rightarrow S_5$ . Here, $S_4$ and $S_5$ belong to the same group $P_2$ . States $S_2$ , $S_4$ , $S_5$ and $S_6$ can be combined.
$1$ -successors – $S_2 \rightarrow S_4$ , $S_4 \rightarrow S_2$ , $S_5 \rightarrow S_3$ and $S_6 \rightarrow S_6$ . Here, $S_2$ , $S_4$ and $S_6$ belong to group $P_2$ but $S_3$ belong to the group $P_1$ . Thus states $S_2$ , $S_4$ and $S_6$ can be combined but $S_5$ is a different state and it is assigned to another partition $P_3$ .

Third Pass :- In the third pass we have three partitions $P_1 = S_0S_1S_3$ , $P_2 = S_2S_4S_6$ and $P_3 = S_5$ . Same steps are followed in this pass also.

Consider the partition $P_1$ and their $k$ -successors are

$0$ -successors – The $0$ -successors are $S_1$ and $S_3$ which belong to same group.
$1$ -successors – The $1$ -successors are $S_2$ , $S_5$ and $S_6$ . Here, $S_2$ and $S_6$ belong to $P_2$ but $S_5$ belong to $P_3$ . Thus $S_1$ can not be combined with $S_0$ and $S_3$ . The state $S_1$ is must be kept in another partition.

Similar analysis can be run for partition $P_2$ and $P_3$ .

After the third pass, the partitions are updated as $P_1 = S_0S_3$ , $P_2 = S_1$ , $P_3 = S_2S_4S_6$ and $P_4 = S_5$ . Further passes can be run but after the third pass there is no change in the partitions. Thus final states are same as result of the third pass. The state minimization result is same as the Implication chart produces as shown in Table 2.

Related Posts