PROFESSOR: This truth table represents
a five-state finite state machine, or FSM,
with a one-bit input, IN, and a two-bit output, OUT.
This FSM is a Mealy machine.
That means that its outputs are a function
of both the current state and the current input.
When this FSM is initialized, its starting state
is state B. We are given a partially filled state
transition diagram shown here.
Our job is to fill in the missing state and transition
labels.
In other words, S1 through S4 should
be replaced with the states A through E. And T1 through T7
should be replaced with a IN/OUT transition corresponding
to that arrow.
In order to do this, we begin by looking at the truth table,
beginning with the starting state
B. The truth table shows us that when IN equals 0,
our next state is state C. Since the 0 input transition out
of state B is already labeled for us,
we know that state S2 equals C. This also tells us that T2
corresponds to IN equals 1.
So S4 is equal to D. And T2 is equal to 1/00.
From state D, we have the one input transition
already labeled.
So T3 corresponds to IN equals 0.
Looking at the truth table, that means that S3
equals E and T3 equals 0/01.
The truth table then shows us that from state E,
a 1 input takes you back to state B.
So T4 equals 1/01, which in turn means that T5 equals 0/10.
And state S1 equals A.
From state A, the 0 input transition
is already filled in.
So T1 equals 1/11.
From state C, a 1 input goes to state B.
So T6 equals 1/01, which in turn means that T7 equals 0/10.
Now that we have a complete state diagram for our FSM,
the next thing we want to figure out is what sequence of outputs
is produced if we begin in state B and receive inputs 1, 0, 0.
Since our state transition diagram is now filled,
we see that from state B, a 1 input takes us to state D
and produces a 00 output.
From state D, a 0 input moves us to state E and outputs 01.
Finally, from state E, a 0 input moves us to state A
and produces a 10 output.
OK.
Now let's try to find a sequence of inputs
that is guaranteed to leave the FSM in state E,
regardless of the state it is in before the sequence is
processed.
To answer this question, we take a look at our filled-in state
diagram and determine what sequence of inputs
takes us from each state X to state E.
We begin with state A. From state A,
the shortest sequence of inputs required to get to state E
is 1, 1, 0.
This takes you from A to B to D to E. Next,
we examine state B. We see that the sequence 1, 0 will take us
from B to D to E. Since we are looking
for a single sequence that will work from all states,
we want to see if 1, 1, 0 would also work.
Taking a closer look at state D shows us
that the sequence 1, 1, 0 will also
get us from B to E because the extra 1 just keeps you in state
D for one extra iteration.
And then the 0 takes you to state E. Similarly,
if you begin at state D, the sequence 1, 1, 0
leaves you at state D for two iterations.
And then on the third, the 0 takes you to state E.
Beginning at state E itself, the sequence 1, 1, 0
takes you to state B, then D, then E.
So we have one state left to check,
and that is state C. From state C,
the sequence 1, 1, 0 takes us to state B, then D, then E.
So once again, the sequence 1, 1, 0 works.
This means that regardless of what state
you start in, the sequence 1, 1, 0 will have you end at state E.
The last question we want to answer about the finite state
machine is whether or not there exists
an equivalent FSM that has only four states instead of five.
In other words, are there two states
that can be merged into one to reduce the FSM to an equivalent
FSM with one fewer state?
Recall that in a Mealy FSM, two states
are equivalent if they have the same input/output
transitions as each other.
If it were a Moore FSM, then the two states
would be equivalent if they produced the same output
and have the same transitions.
Taking a closer look at the states in this FSM,
we see that both states C and E transition to state B on a 1
input and produce a 01 output.
On a 0 input, they both transition to state A
and produce a 10 output.
So states C and E are equivalent and can
be merged into a single state, thus reducing the total number
of states in our FSM to four.