| Present State |
Next State |
Output |
| |
$x=0$ $x=1$ |
$x=0$ $x=1$ |
| a |
f b |
0 0 |
| b |
d c |
0 0 |
| c |
f e |
0 0 |
| d |
g a |
1 0 |
| e |
d c |
0 0 |
| f |
f b |
1 1 |
| g |
g h |
0 1 |
| h |
g a |
1 0 |
Two states are said to be equivalent if, for each member of the set of inputs, they give exactly the same output and send the circuit either to the same state or to an equivalent state. When two states are equivalent, one of them can be removed without altering the input-output relationships.
Going through the state table, we look for two present states that go to the same next state and have the same output for both input combinations.
States $h$ and $d$ are two such states. They both go to states $g$ and $a$ and have outputs of $1$ and $0$ for $x = 0$ and $x = 1,$ respectively. Therefore, states $h$ and $d$ are equivalent, and one of these states can be removed.
Now we can remove present state $h$ and replace by $d$ each time.
| Present State |
Next State |
Output |
| |
$x=0$ $x=1$ |
$x=0$ $x=1$ |
| a |
f b |
0 0 |
| b |
d c |
0 0 |
| c |
f e |
0 0 |
| d |
g a |
1 0 |
| e |
d c |
0 0 |
| f |
f b |
1 1 |
| g |
g a |
0 1 |
Again we got, states $e$ and $b$ are two such states. They both go to states $d$ and $c$ and have outputs of $0$ and $0$ for $x = 0$ and $x = 1,$ respectively. Therefore, states $e$ and $b$ are equivalent, and one of these states can be removed.
Now we can remove present state $e$ and replace by $b$ each time.
| Present State |
Next State |
Output |
| |
$x=0$ $x=1$ |
$x=0$ $x=1$ |
| a |
f b |
0 0 |
| b |
d c |
0 0 |
| c |
f b |
0 0 |
| d |
g a |
1 0 |
| f |
f b |
1 1 |
| g |
g a |
0 1 |
gain we got, states $c$ and $a$ are two such states. They both go to states $f$ and $b$ and have outputs of $0$ and $0$ for $x = 0$ and $x = 1,$ respectively. Therefore, states $c$ and $a$ are equivalent, and one of these states can be removed.
Now we can remove present state $c$ and replace by $a$ each time.
| Present State |
Next State |
Output |
| |
$x=0$ $x=1$ |
$x=0$ $x=1$ |
| a |
f b |
0 0 |
| b |
d a |
0 0 |
| d |
g a |
1 0 |
| f |
f b |
1 1 |
| g |
g a |
0 1 |
If we again apply the algorithm, then we can't find such types of states. So the final reduced state table is:
| Present State |
Next State |
Output |
| |
$x=0$ $x=1$ |
$x=0$ $x=1$ |
| a |
f b |
0 0 |
| b |
d a |
0 0 |
| d |
g a |
1 0 |
| f |
f b |
1 1 |
| g |
g a |
0 1 |
