State Equivalence & Minimization Part – 2

The states which are equivalent, are redundant. Because by looking at the output, we can not even figure out in which state the machine is in. So, if there are two equivalent states then there is no point of using both the states. We can merge both the states and can use only one state.

Steps for State Machine Minimization

• Identify equivalent states
• Replace equivalent states by one state.

Theorem for State Equivalence

Two states S_i and S_j are k+1 equivalent if and only if

• They are k-equivalent
• And their next states for all inputs are k-equivalent

If we have a set of states which are k-equivalent, then a subset of these, which may include all of them or none of them are only going to be k+1 equivalent. There can not be another state coming in, which is not k-equivalent and that is k+1-equivalent.

So as we increase the “k”, set of distinguishable states grows and set of equivalent states reduces.

Minimization Steps

• Consider all states to be 0-equivalent
• Identify 1-equivalent partition P₁ based on outputs
• Identify i+1 equivalent partition P_i+1 based on P_i until (P_i+1 = P_i)
• Replace each set of states in a P_i class by a single state and define the state transitions accordingly

Procedure

• For generating P₁ we have to look for outputs
• For generating P₂, P₃, P₄ and so on we have to look whether the two states belong to the same equivalent class as far as P_i is concerned and whether the next states for any input belong to the same class or not. If they belong to the same class then they will be P_i+1 equivalent.
• So for this procedure we only have to bother about next state transition and we don’t have to bother about output. We will keep on generating this until P_i+1 = P_i (i.e, at some stage if we are not able to get any more states to be distinguishable). This is because if P_i+1 = P_i then P_i+2 = P_i+1. So, there is no point of moving further
• Once this condition reach, then replace each set of states in a P_i class by a state and define state transitions accordingly

All the members in a class of P_i partition are i-equivalent.

If the initial state diagram does not have any redundancy, all the states will become a class in itself and the partition will contain as many number classes as the number of states.

Let’s consider an example of Machine M1 representing the following state table

PS	NS, z
	x=0	x=1
A	E,0	D,1
B	F,0	D,0
C	E,0	B,1
D	F,0	B,0
E	C,0	F,1
F	B,0	C,0

Now the State partitions for the above state table will be as follows:

Symbol	Partition
P0	(A B C D E F)
P1	(A C E) (B D F)
P2	(A C E) (B D) (F)
P3	(A C) (E) (B D) (F)
P4	(A C) (E) (B D) (F)

The above state partition shows the states “A” and “C” are equivalent and states”B” and “D” are equivalent. So we can merge state “A” and “C” to one state, similarly state “B” and “D” can be merged.

Let’s discuss some of the class divisions from partition P₁ to P₂ for better understanding:

P₁ to P₂

The set of states which lie under P₁, form 1-equivalent class. That means all the states in one class/set are 1-equivalent. This shows A, C and E are 1-equivalent and similarly B, D and F are 1-equivalent.

Now while trying to creating the P2 partition;

• For A and C, and for the input x=0; next states are same, that is E and E respectively. For input x=1; next states are D and B. As D and B lie in same class, we can conclude that A and C are 2-equivalents.
• For A and E, and for the input x=0; next states are E and C respectively, which lie in the same class. For input x=1; next states are D and F, which again lie in the same class. So, we can conclude that A and E are 2-equivalents.
• For B and F, and for the input x=0; next states are F and B respectively, which lie in the same class. For input x=1; next states are D and C, which do not lie in the same class. So, we can conclude that B and F are not 2-equivalent but 2-distinguishable. So we can see in partition P₂, B lies in a different set and F lies in a different set.

You can analyze all other state combinations and find out the above partition table. if any doubt please drop a comment at the below section.

Read State Equivalence & Minimization Part – 3, to see how a state transition diagram gets minimized using the above minimization method.