State Partition Method for State Minimization

By | 10th September 2021

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.

Table 1: Example State Table

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

  1. 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.
  2. 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

  1. 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.
  2. 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

  1. 0-successors – The 0-successors are S_1 and S_3 which belong to same group.
  2. 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.

Table 2: Optimized state table
(Visited 26 times, 1 visits today)

Leave a Reply

Your email address will not be published. Required fields are marked *