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

  1. The outputs must be same for both the states.
  2. 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.

(Visited 486 times, 1 visits today)
Shopping Cart