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 Si and Sj 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 P1 based on outputs
- Identify i+1 equivalent partition Pi+1 based on Pi until (Pi+1 = Pi)
- Replace each set of states in a Pi class by a single state and define the state transitions accordingly
Procedure
- For generating P1 we have to look for outputs
- For generating P2, P3, P4 and so on we have to look whether the two states belong to the same equivalent class as far as Pi 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 Pi+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 Pi+1 = Pi (i.e, at some stage if we are not able to get any more states to be distinguishable). This is because if Pi+1 = Pi then Pi+2 = Pi+1. So, there is no point of moving further
- Once this condition reach, then replace each set of states in a Pi class by a state and define state transitions accordingly
All the members in a class of Pi 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 P1 to P2 for better understanding:
P1 to P2
The set of states which lie under P1, 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 P2, 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.
Once Hopcroft’s algorithm has been used to group the states of the input DFA into equivalence classes, the minimum DFA can be constructed by forming one state for each equivalence class.