Row Equivalence Method for State Minimization

Row Equivalence Method for State Minimization is a very simple technique to reduce number of states of an FSM. In the row equivalence method, it is checked that rows of a state table are equivalent or not. Here, a comparatively strict definition of state equivalence is used. The conditions for two states $S_1$ and $S_2$ to be equivalent are

The outputs must be same for both the states.
The $k$ -successors must be same for all the input conditions.

Table 1: State table example for state minimization.

Row Equivalence Method is explained here with the help of the state table shown in Table 1. Here, states $S_1$ and $S_5$ can be said equivalent as their output is same and their $k$ -successors are also same. Similarly, the states $S_2$ , $S_4$ and $S_6$ are equivalent. Thus using this simple state minimization technique the state table is reduced to the state table as shown in Table 2. Here, $S^*_1$ is written for states $S_1$ and $S_5$ . Similarly, $S^*_2$ is written for states $S_2$ , $S_4$ and $S_6$ .

Table 2: Minimization of state table shown in Table 1 using Row Equivalent

Row Equivalence Method is a simple technique for state minimization but it does not always lead to optimized number of states.

Related Posts