1

FINITE STATE MACHINES

SOLVED EXAMPLES
Example 3.1 Construct a Mealy machine equivalent to Moore machine M 1=(Q, , , , ,
s) described in following transition table.

Inputs
0 1
PS NS NS Output
s q3 q1 0
q1 q1 q2 1
q2 q2 q3 0
q3 q3 s 0

Solution: Let equivalent Mealy machine M2=(Q, , , , , s), where

Q={s, q1, q2, q3}, ={0, 1}, ={0, 1}, and  is defined as following:
For state s: (s, 0) = ((s, 0)) = (q3) = 0
(s, 1) = ((s, 1)) = (q1) = 1
For state q1: (q1, 0) = ((q1, 0)) = (q1) = 1
(q1, 1) = ((q1, 1)) = (q2) = 0
For state q2: (q2, 0) = ((q2, 0)) = (q2) = 0
(q2, 1) = ((q2, 1)) = (q3) = 0
For state q3: (q3, 0) = ((q3, 0)) = (q3) = 0
(q3, 1) = ((q3, 1)) = (s) = 0

Transition is same for both machines, and s is the starting state.

Transition table:
Inputs
0 1
PS NS Output NS Output
s q3 0 q1 1
q1 q1 1 q2 0
q2 q2 0 q3 0
q3 q3 0 s 0
 2

Example 3.2 Construct a Moore machine equivalent to Mealy machine M 1=(Q, , , , ,

s) described in following transition table.

Inputs
0 1
PS NS Output NS Output
s s1 z1 s2 z1
s1 s1 z2 s2 z1
s2 s1 z1 s2 z2

Solution: Let M1=(Q, , , , , s) is given Mealy machine and M2=(Q, , , , , s)
be the equivalent Moore machine, where
1. Q{[s, z1], [s, z2], [s1, z1], [s1, z2], [s2, z1], [s2, z2]} (Since, QQ),
2. ={0, 1},
3. ={z1, z2},
4. Let starting state s=[s, z1], where s is the initial state and z1 is the output symbol of
Mealy machine,
5.  is defined as follows:
For initial state [s, z1]: ([s, z1], 0)=[(s, 0), (s, 0)] = [s1, z1]
([s, z1], 1)=[(s, 1), (s, 1)] = [s2, z1]
(Note: Both states [s1, z1] and [s2, z1] are reachable from initial state.)
For state [s1, z1]: ([s1, z1], 0)=[(s1, 0), (s1, 0)] = [s1, z2]
([s1, z1], 1)=[(s1, 1), (s1, 1)] = [s2, z1]
For state [s2, z1]: ([s2, z1], 0)=[(s2, 0), (s2, 0)] = [s1, z1]
([s2, z1], 1)=[(s2, 1), (s2, 1)] = [s2, z2]
(Note: Both states [s1, z2] and [s2, z2] are reachable states.)
For state [s1, z2]: ([s1, z2], 0)=[(s1, 0), (s1, 0)] = [s1, z2]
([s1, z2], 1)=[(s1, 1), (s1, 1)] = [s2, z1]
For state [s2, z2]: ([s2, z2], 0)=[(s2, 0), (s2, 0)] = [s1, z1]
([s2, z2], 1)=[(s2, 1), (s2, 1)] = [s2, z2]
(Note: We have considered those states, which are reachable from initial state.)
6.  is defined as follows:
 3

[s, z1]= z1, [s1, z1]= z1, [s2, z1]= z1, [s1, z2]= z2, [s2, z2]= z2
Transition Table:
Inputs
0 1
PS NS NS Output
[s, z1] [s1, z1] [s2, z1] z1
[s1, z1] [s1, z2] [s2, z1] z1
[s2, z1] [s1, z1] [s2, z2] z1
[s1, z2] [s1, z2] [s2, z1] z2

Example 3.4 Design a Moore machine, which outputs residue mod 3 for each binary input
string treated as a binary integer.
Solution: Let Moore machine M=(Q, , , , , q0), where
={0, 1}, ={0, 1, 2} (outputs after mod 3),
Let three states {q0, q1, q2} are there and
 State q0 outputs 0,
 State q1 outputs 1, and
 State q2 outputs 2.
If input is binary string X, then

X is followed by a 0 is equivalent to twice of X.

X is followed by a 1 is equivalent to twice of X plus 1.
Or
X0(2X)10 (in decimal system), and
X1(2X)10  1 (in decimal system)
If X mod 3=p, for p=0 or 1 or 2, then
X0 mod 3=2p mod 3 (For input 0)
=0 or 2 or 1
For transition:
qpq2*p mod 3 for p=0, 1, 2
X1 mod 3=(2p+1) mod 3 (For input 1)
=1, 0, 2
For transition:
 4

qpq(2*p +1) mod 3 for p=0, 1, 2

0 1

0 1
q1 q1 q2
1

O/P=0 O/P=1 0 O/P=2

Fig. 3.29 Transition Diagram

Example 3.7 Consider the following transition table of a Mealy machine. Construct
minimum state Mealy machine

0 1
PS NS Output NS Output
q1 q1 0 q2 0
q2 q1 0 q3 1
q3 q1 0 q3 1

Solution: Last two rows of transition table show that states q2 and q3 are equivalent states.
So, replacing these states by [q2, q3] we have the following intermediate transition table:

0 1
PS NS Output NS Output
q1 q1 0 [q2, q3] 0
[q2, q3] q1 0 [q2, q3] 1
[q2, q3] q1 0 [q2, q3] 1

Deleting the last row, we have the following final transition table:

Inputs
0 1
PS NS Output NS Output
q1 q1 0 [q2, q3] 0
[q2, q3] q1 0 [q2, q3] 1

Example 3.8 Consider following Mealy machine described in following transition table.
Construct equivalent minimum state Mealy machine.
 5

0 1
PS NS Output NS Output
a a 0 b 0
b c 0 d 0
c a 0 f 0
d e 0 f 1
e a 0 f 1
f g 0 f 1
g a 0 f 1

Solution: State e and g (row 7 and row 5) are equivalent states. So replacing e and g by [e,
g], we have the following intermediate transition table:

Inputs
0 1
PS NS Output NS Output
a a 0 b 0
b c 0 d 0
c a 0 f 0
d [e, g] 0 f 1
[e, g] a 0 f 1
f [e, g] 0 f 1
[e, g] a 0 f 1

Now, states d and f (row 4 and 6) are equivalent states. So, replacing these states by [d,
f], we have the following transition table:

Inputs
0 1
PS NS Output NS Output
a a 0 b 0
b c 0 d 0
c a 0 [d, f] 0
[d, f] [e, g] 0 [d, f] 1
[e, g] a 0 [d, f] 1
[d, f] [e, g] 0 [d, f] 1
[e, g] a 0 [d, f] 1

Now, we have no more equivalent states. Removing the redundancy from the above
transition table, we have the following final transition table:
 6

Inputs
0 1
PS NS Output NS Output
a a 0 b 0
b c 0 d 0
c a 0 [d, f] 0
[d, f] [e, g] 0 [d, f] 1
[e, g] a 0 [d, f] 1

Example 3.9 Full adder shown in Fig. 3.31 receives two external inputs x and y; the third
input z comes from the output of a D flip-flop. The carry output is transferred to the flip-
flop every clock pulse. The external output gives the sum of x, y, and z. Obtain the
Transition diagram of the sequential circuit.

x Full S
y Adder
Carry
Q
z D

Clock Pulse
Fig. 3.31 Full adder

Solution: One flip-flop is used, so it may be in state 0 or 1. Inputs are x, y, and z, so eight
different possible combinations are there. When carry=0 (or D=0), then state 0 is reachable
otherwise state 1 is reachable.

State Input Output (Sum) Carry Next State

xyz D
0 00 0 0 0 0
0 01 0 1 0 0
0 10 0 1 0 0
0 11 0 0 1 1
1 00 1 1 0 0
1 01 1 0 1 1
1 10 1 0 1 1
1 Transition
11 1 diagram:
1 1 1
 7

00/0, 01/1, 10/1 01/0, 10/0, 11/1

11/0
0 1
00/1

Fig. 3.32 Full adder

Example 3.12 Convert the following Mealy machine (Fig. 3.36) into equivalent Moore
machine. b/1

q1

a/0 a/1

a/1 q2
q0
a/0 b/1
b/0
b/1 q3

Fig. 3.36

Solution: Let M1=(Q, , , , , q0) is a given Mealy machine and M2=(Q, {a, b},
(0, 1}, , , s) be the equivalent Moore machine, where
Q{[q0, 0], [q0, 1], [q1, 0], [q1, 1], [q2, 0], [q2, 1], [q3, 0], [q3, 1]} (Since, QQ),
s=[q0, 1], where q0 is the initial state and 1 is one the output symbol of Mealy machine,
Transition function  is defined as following:

Next State
Present State a b Output
[q0, 0] [q2, 1] [q3, 0] 0
[q2, 1] [q1, 1] [q2, 0] 1
[q3, 0] [q2, 0] [q0, 1] 0
[q1, 1] [q0, 0] [q1, 1] 1
[q2, 0] [q1, 1] [q2, 0] 0
[q0, 1] [q2, 1] [q3, 0] 1

Equivalent Moore machine is shown in Fig. 3.36(a).

 8

O/P=0 b
[q0, 0] [q3,0]
b [q0,1]
b
O/P=0
a a a O/P=1

O/P=1 [q2,1]
[q2,0]
b b
a
a O/P=0
O/P=1 [q1,1]

a
b
O/P=0
[q0,0]
Fig. 3.36(a)

Example 3.13 Change the given Moore machine into Mealy machine:

q0/1 q1/0
b
a
b b a
a
q3/1 q2/0
a
b

Fig. 3.37 Moore Machine

Solution: Let M1=(Q, , , , , q0) be the given Moore machine, where transitions and
output is as follows:
a b
Present State (PS) Next State (NS) Next State (NS) Output
q0 q2 q3 1
q1 q3 q2 0
q2 q1 q2 0
q3 q2 q1 1
 9

Let equivalent Mealy machine M2=(Q, , , , , s) as shown in Fig. 3.37(a), where
Q={q0, q1, q2, q3}, ={a, b}, ={a, b},  is defined as following:
Inputs
0 1
PS NS Output NS Output
q0 q2 0 q3 1
q1 q3 1 q2 0
q2 q1 0 q2 0
q3 q2 0 q1 0

q0 q1
b/0
a/0 a/0
b/1 b/0
a/1
q3 q2
a/0
b/0

Fig. 3.37(a) Mealy Machine

SUPPLEMENTARY PROBLEMS:
3.21 Design Moore and Mealy machines that do the following:
(a) Reads input binary number and outputs in binary such that the output is one greater
than the input.
(b) Reads input binary number and outputs in binary such that the output is one less than
the input.
(c) Recognize the strings over (a+b)* and output (EVEN, EVEN), (ODD, ODD), (EVEN,
ODD), or (ODD, EVEN) according to the number of a’s and b’s.
3.22 Draw transition diagram of Mealy machine which reads string over (a+b)* and does
the following:
(a) Produces output an, where n is the number of occurrence substring ab.
(b) Produces output an, where n is the number of occurrence substring aba.
3.23 Design a FSM which checks input whether it is even or odd. Assume that input is
provided in decimal.
 10

3.24 Consider the 3-bit binary counter shown in Fig. 3.25 and draw the logic diagram using:
T Flip-flops, D Flip-flops, SR Flip-flops

3.34 Compare the Moore and Mealy machines and prove that both machines have
equivalent power.
3.35 What is difference between finite automaton (FA) and finite state machines?
3.36 Discuss how the finite state machines are used in designing of synchronous sequential
circuits.
3.37 What are equivalent finite state machines? How a finite state machine is minimized?
3.38 Consider the transition diagram of the binary subtraction shown in Fig. 3.43. Draw
the logic circuit diagram.

00/0 01/1
01/1
10/1 B=0 B=1

00/0, 10/1, 11/0

10/1
Fig. 3.43 Binary Subtraction

3.39 Describe the finite state machine. How Moore and Mealy machines are
mathematically described?