The Gateway to Computer Science Excellence
+1 vote
55 views

Reduce the number of states in the following state table and tabulate the reduced state table.

in Digital Logic by Boss (10.5k points) | 55 views

1 Answer

0 votes
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
by Veteran (54.8k points)
edited by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,492 answers
195,439 comments
100,696 users