State Equivalence & Minimization Part – 1

Sometimes a state diagram constructed for a finite state machine contains redundant states, i.e. states whose function can be accomplished by other states. The number of memory elements required for the realization of a machine is directly related to the number of states. Consequently, the minimization of the number of states does reduce the complexity and cost of the realization in many cases. Moreover, the testing of the sequential machine is considerably simpler when the machine does not contain redundant states. Therefore, methods should be developed to find out the redundant states and minimize the state diagram while maintaining the same terminal behavior.

Important Terminologies related to State Minimization

• Equivalent States
• Distinguishable States
• k-equivalent States
• k-distinguishable States

Two states, S_i or S_j, of a machine M are distinguishable if and only if there exists at least one finite input sequence that when applied to M, causes different output sequences depending on whether S_i and S_j are the initial state.

The sequence that distinguishes these states is called a distinguishing sequence for the pair (S_i, S_j).

If there exists a distinguishing sequence of length “k” for the pair (S_i, S_j), then S_i, S_j are said to be k-distinguishable.

The states S_i or S_j are said to be equivalent if for any length of input pattern, looking towards the output sequence we can not distinguish whether the machine starts from state S_i or S_j (i.e, equal output sequences of both the states for all the inputs.)

The states which are equivalent for input sequence of length “k” are known as k-equivalent States.

Rule

(i) Always the equivalency or distinguish-ability are decided between a pair of states.

(ii) For the input sequence of length “0”, we consider all the states are 0-equivalent

Findings

(i) The states S_i and S_j of machine M are said to be equivalent if and only if, for every possible input sequence, the same output sequence is produced regardless of whether S_i or S_j is the initial state.

(ii) States which are k+1-equivalent are k-equivalent

(iii) States which are k-distinguishable are k+1-distinguishable

(iv) For equivalent; pair of states should be equivalent for all input patterns

(v) For distinguishable; pair of states should be distinguishable for at-least one input pattern

Let’s consider the Parity Generator Example

Looking at the state diagram we can say that the states S0 and S1 are 1-distinguishable. Let’s say there are two machines M0 starts at state S0 and M1 starts at state S1. If we would provide “0” as input to both the machines then M0 would produce an output “0” and M1 would produce an output “1”. The out put sequences generated for the 1-bit input “0” are different for both the machines. So the machines are 1-distinguishable.

Let’s consider the Sequence detector Example

• S0, S1 and S2 are 1-equivalent
• S0 and S1 are 2-equivalent
• S2 and S3 are 1-distinguishable

---

Read State Equivalence & Minimization Part – 2, to know Minimization steps.