TOC Reference

Theory of Computation Solutions for review questions
Author: Vivek Kulkarni

( [email protected] )
Chapter-2: Finite State Machines
Solutions for Review Questions
@ Oxford University Press 2013. All rights reserved. 1

Q.1 Construct Mealy and Moore machines for the following:

For the input from *, where  = {0, 1, 2} print the residue-modulo-5 of the input treated as a
ternary (base 3 with digits 0, 1, and 2) number.
Solution:
Refer to the example 2.21 from the book.
Q.2 Discuss the relative powers of NFA and DFA.
Solution:
NFA (Non-deterministic Finite Automata) and DFA (Deterministic Finite Automata) are equivalent to
each other. Each NFA can be converted to its equivalent DFA, which means, NFA and DFA are of the
same power in terms of acceptance of language and state transitions depending upon given input over
language alphabets.
We can show equivalence relation in NFA and DFA by drawing NFA and its equivalent DFA as follows.
Above NFA shows two transitions for an input symbol 0 from state q0. This NFA only accepts strings
“00” and “01”, which means language accepted by the NFA can be given as,
L1 = {00, 01}
Hence state q1 can be removed from the equivalent DFA as it is not reaching final state q2 on any
symbol. Equivalent DFA accepts same language,
L2 = {00, 01}
As L1 = L2, NFA and DFA drawn above are equivalent and accept the same language. Therefore their
power is same.

Q.3 Write the machine function and the state transition function for a binary adder. Support your
answer with a transition diagram.
Solution:
Q.4 Prove the following:

“Corresponding to every transition graph, there need not exist an FSM, but the converse is always
true”.
Solution:
Refer to the section 2.3.6, theorem 2.1.
Q.5 Define and give suitable examples for a transition graph.
Solution:
Transition Graph (or Transition Diagram) is a directed graph whose vertices corresponds to the states of
the Finite State Machine and directed edges corresponds to the transitions from one state to another state
on the acceptance of input symbol which is written above the directed edge. Refer section 2.3.1 for
details. Refer to the solution of question Q.3 above for the example of transition graph.
Q.6 Construct a Mealy machine that accepts the strings from (0 + 1)* and produces the output as
indicated below:
End of string Output
101 x
110 y
Otherwise z
Solution:
Q.7 Explain whether a language of palindromes is accepted by an FSM. Justify.
Solution:
Refer to the section 2.14.

Q.8 Describe the following:

(a) State equivalence
(b) FSM equivalence
Solution:
(a) State equivalence – Refer to the section 2.6.2.1.
(b) FSM equivalence – Refer to the section 2.12.
Q.9 Write a short note on Mealy and Moore machines.
Solution:
Q.10 Explain with an example, the process of converting a Mealy machine to its corresponding Moore
machine.
Solution:
Refer to the section 2.11.2.
Q.11 Write a short note on the properties and limitations of FSM.
Solution:
Q.12 Compare Moore and Mealy machines.
Solution:
Q.13 Design an FSM to check divisibility by three, where  = {0, 1, ..., 9}.
Solution:

Q.14 What are finite automata? Construct the minimum state automata equivalent to following state
transition diagram:
Figure 2.51: Example automata
Solution:
We can see from the figure that the states q4, q5, q6 and q7 are not reachable from the initial state, as there
is no path from the initial state that reaches to these states. We can easily remove these 4 states and their
transitions as they do not take part in any string acceptance.
Hence, we are left with the reduced FA as shown in the diagram below,
Let us now draw the STF form the above TG. The STF is,
Q\ a b
q0 q1 q0
q1 q0 q2
q2 q3 q1
*q3 q3 q0
As we can see, there are no more states that we can reduce and hence, it is the answer.

Q.15 Construct NFA without -transitions for the following NFA with -transitions.
Figure 2.52: Example NFA with -transitions
Solution:
Let us first find the -closure of all the states. Let us assume that q0 is the initial state of the NFA given.
-closure (q0) = {q0, q1}
-closure (q1) = {q1}
-closure (q2) = {q2, q3, q5}
-closure (q4) = {q4, q3, q5}
-closure (q3) = {q3, q5}
q7 is the only final state even for the NFA without -transitions.
Now let us find transition function ' for the resultant NFA. This can be obtained by using rule:
' (q, a) = -closure ((^ (q, ), a))
Therefore,
' (q0, a) = -closure ((^ (q0, ), a))
= -closure (({q0, q1}, a))
= -closure ((q0, a) U (q1, a))
= -closure (Uq2
  -closure (q2)
= {q2, q3, q5}
We can obtain all the other transitions. The transition table for the resultant NFA is,

Q\∑ a b
q0 {q2, q3, q5} {q4, q3, q5}
q1 {q2, q3, q5} {q4, q3, q5}
q2 {q6} 
q3 {q6} 
q4 {q6} 
q5 {q6} 
q6  {q7}
* q7  
Q.16 Design an FSM that reads strings made up of letters in the word ‘CHARIOT’ and recognizes
those strings that contain the word ‘CAT' as a substring.
Solution:
Q.17 Construct a Moore machine equivalent to the Mealy machine represented by the following TG:
Figure 2.53: Example Mealy machine
Solution:
Let us draw state function and machine function for the given Mealy machine.

Q\ 0 1 Q\ 0 1
q1 q2 q3 q1 z1 z2
q2 q2 q3 q2 z2 z1
q3 q2 q3 q3 z1 z2
 : Q x   Q (State function)  : Q x    (Machine function)
According to the rule of conversion, the resultant Moore machine consists of states:
Q' = Q x  = {[q1, z1], [q1, z2], [q2, z1], [q2, z2], [q3, z1], [q3, z2]}
Also ' and ' can be found as follows:
a) '([q1, z1], 0) = [ (q1, 0),  (q1, 0)]
= [q2, z1]
'([q1, z1], 1) = [ (q1, 1),  (q1, 1)]
= [q3, z2]
'([q1, z1]) = z1
b) '([q1, z2], 0) = [ (q1, 0),  (q1, 0)]
= [q2, z1]
'([q1, z2], 1) = [ (q1, 1),  (q1, 1)]
= [q3, z2]
'([q1, z2]) = z2
c) '([q2, z1], 0) = [ (q2, 0),  (q2, 0)]
= [q2, z2]
'([q2, z1], 1) = [ (q2, 1),  (q2, 1)]
= [q3, z1]
'([q2, z1]) = z1
d) '([q2, z2], 0) = [ (q2, 0),  (q2, 0)]
= [q2, z2]
'([q2, z2], 1) = [ (q2, 1),  (q2, 1)]
= [q3, z1]
'([q2, z2]) = z2

e) '([q3, z1], 0) = [ (q3, 0),  (q3, 0)]

= [q2, z1]
'([q3, z1], 1) = [ (q3, 1),  (q3, 1)]
= [q3, z2]
'([q3, z1]) = z1
f) '([q3, z2], 0) = [ (q3, 0),  (q3, 0)]
= [q2, z1]
'([q3, z2], 1) = [ (q3, 1),  (q3, 1)]
= [q3, z2]
'([q3, z2]) = z2
Q.18 Consider the DFA as shown in the Fig. 2.54. Obtain the minimum state DFA.
Figure 2.54: Example DFA
Solution:
Q.19 Consider the Moore machine described by the transition table given below. Construct the
corresponding Mealy Machine.
Current Next state
state
a = 0 a = 1 Output
 q1 q1 q2 0
q2 q1 q3 0
q3 q1 q3 1

Solution:
Q.20 Construct a DFA equivalent to the NFA: ({p, q, r, s}, {0, 1}, , p, {q, s}), where ‘’ is given by:
Solution:
Q.21 Write and explain all the steps required for the conversion of an NFA to a DFA using a suitable
example.
Solution:
Q.22 Convert the following Mealy machine to a Moore machine.
Solution:
Q\ a b Q\ a b
S0 S1 S0 S0 0 0
S1 S1 S0 S1 1 1
According to the rule of conversion, the resultant Moore machine consists of states:
Q' = Q x  = {[S0, 0], [S0, 1], [S1, 0], [S1, 1]}


a) '([S0, 0], a) = [ (S0, a),  (S0, a)]
= [S1, 0]
'([S0, 0], b) = [ (S0, b),  (S0, b)]
= [S0, 0]
'([S0, 0]) = 0
b) '([S0, 1], a) = [ (S0, a),  (S0, a)]
= [S1, 0]
'([S0, 1], b) = [ (S0, b),  (S0, b)]
= [S0, 0]
'([S0, 1]) = 1
c) '([S1, 0], a) = [ (S1, a),  (S1, a)]
= [S1, 1]
'([S1, 0], b) = [ (S1, b),  (S1, b)]
= [S0, 1]
'([S1, 0]) = 0
d) '([S1, 1], a) = [ (S1, a),  (S1, a)]
= [S1, 1]
'([S1, 1], b) = [ (S1, b),  (S1, b)]
= [S0, 1]
'([S1, 1]) = 1
Q.23 Consider the following NFA with -transitions. Assume ‘p’ to be the initial state and ‘r’ as the
final state.
 a b c
p  {p} {q} {r}
q {p} {q} {r} 
r {q} {r}  {p}
1) Compute the -closure of each state

2) List all the strings of length three or less accepted by the automata
3) Convert the automaton to its equivalent DFA

Solution:
Let us first draw the TG for the given NFA with -transitions.
1) -closure (p) = {p}

-closure (q) = {p, q}
-closure (r) = {p, q, r}
2) All the strings of length three or less accepted by the automata

= {c, ac, bb, bc, ca, cb, cc, abb, abc, bab, bac, aca, acb, acc, caa, cbb, ccc, cab, cba, cac, cca, cbc,
ccb}
3) The equivalent DFA can be obtained using a direct method as below. Each state has the primary
as well as the secondary label. Secondary label consists of all the reachable states from the given
state. We also have relabelled the states from 1 to 7, out of which 4, 5, 6 and 7 are final states.
Let us also refer to the STF drawn and see whether it can be reduced.

a b c
1 1 2 4
2 3 5 4
3 3 5 4
*4 6 5 7
*5 6 5 7
*6 6 5 7
*7 6 5 7
One can see that states 4, 5, 6 and 7 are equivalent. Hence, we can keep only 4 and remove the others by
replacing all their occurrence by 4. Similarly, 2 and 3 are also equivalent; hence, 3 can be removed in lieu
of state 2. Therefore, the reduced STF is,
a b c
1 1 2 4
2 2 3 4
*4 4 4 4
The reduced state DFA is,

Q.24 Construct a DFA for the NFA, whose state transition function is given below. Assume ‘p’ to be
the initial state and F = {q, r}.
0 1
p {p, q} 
q r s
f s 
s s s
Solution:
Initial state for the resultant DFA is also p and set of states Q’ = 2Q.
Hence, Q’ = {p, q, r, s, pq, pr, ps, qr, qs, rs, pqr, pqs, prs, qrs, pqrs}
For the given NFA, set of Final states is given as {q, r}.
Hence, set of final states for the resultant DFA is, F’= {q, r, pq, pr, qr, qs, rs, pqr, pqs, prs, qrs, pqrs}
When two or more symbols represent one state, transition for the resultant DFA can be obtained as
follows,
'(pq, 0) = [ (p, 0) ∪  (q, 0)] = [{p,q} ∪ {r}] = pqr
Thus, the STF for the resultant DFA can be written as below,

Q\ 0 1
(1) p pq 
(2) *q r s
(3) *r s 
(4) s s s
(5) *pq pqr s
(6) *pr pqs 
(7) ps pqs s
(8) *qr rs s
(9) *qs rs s
(10) *rs s s
(11) *pqr pqrs s
(12) *pqs pqrs s
(13) *prs pqs s
(14) *qrs rs s
(15) *pqrs pqrs s
We also have relabelled the states from (1) to (15).
We can see that states, (11), (12) and (15) are equivalent. Also, (8), (9) and (14) are equivalent. If we
remove states (12) and (15) and replace all occurrences of them by (11) we can get the reduced state
DFA. Similarly, we can remove (9) and (14) and keep (8) instead. The reduced table would look like,

Q\ 0 1
(1) p 5 -
(2) *q 3 4
(3) *r 4 -
(4) s 4 4
(5) *pq 11 4
(6) *pr 11 -
(7) ps 11 4
(8) *qr 10 4
(10) *rs 4 4
(11) *pqr 11 4
(13) *prs 11 4
From the reduced state table we can see that states (5), (11) and (13) are equivalent. Hence, (11) and (13)
can be removed and their occurrences can be replaced by (5) to obtain the reduced state DFA.
Q\ 0 1
1 5 -
* 2 3 4
* 3 4 -
4 4 4
* 5 5 4
* 6 5 -

7 5 4
* 8 10 4
* 10 4 4
The TG for the DFA can be drawn as,
One can see that states 2, 3, 6, 7, 8 and 10 are no reachable from the initial state. Hence, they do not take
part in the language recognition and hence can be removed being redundant. Also, state 4 though is
reachable from the initial state does not involve in the acceptance and it does not lead to any final state. It
is a trap state. Hence, needs to be removed as well.
Removing all the unwanted states the final TG for the resultant DFA is,
Q.25 Explain Moore and Mealy machines using suitable examples. How do we construct the equivalent
Mealy machine for a given Moore machine? Give a suitable example.
Solution:
Refer to the section 2.11.1.

Q.26 Compare Mealy and Moore machines. Design a Mealy machine to replace each occurrence of
sub-string ‘abb’ by ‘aba’, where  = {a, b}.
Solution:
Refer to the section 2.11 for Mealy and Moore machine comparison.
We need to design a Mealy machine which will replace substring ‘abb’ by ‘aba’.
 Let us assume that initial state of the machine is q0. As none of the substrings start with symbol
‘b’, all such ‘b’s will be read and ignored by the machine in state q0.
 Transition to state q1 is made after reading the input symbol ‘a’ where subsequent input will be
checked. As we have to replace substring, only matching pattern should be replaced and other
patterns should be kept intact as they are.
 State q1 will check for the next input after previous input symbol ‘a’ that is read and will transit to
state q2 if ‘b’ is the input symbol read. Otherwise no transition is made.
 In state q2 it checks if input is ‘b’ (thus satisfying the required pattern ‘abb’) and transits to state
q1 with replacing ‘b’ by ‘a’ and continue the process for each such pattern.
State function and the machine function for the required mealy machine are shown below.
Q\ a b Q\ a b
q0 q1 q0 q0 a b
q1 q1 q2 q1 a b
q2 q1 q1 q2 a a
The transition diagram for the mealy machine is as shown below,

Q.27 Design a Moore machine that changes all the vowels to ‘$’.
Solution:
This is a very simple sequence detector problem. Let  = {A, B, C, …, Z}.
It is required that the vowels from any word, i.e., {A, E, I, O, U} needs to be replaced by ‘$’.
Let us label all the remaining symbols except the vowels as ‘#’ for the simplicity. Using this convention
Moore machine can be drawn as,
As we can see from the TG that state p is associated with the output ‘#’ which indicates no change in the
symbol if it is any other character than the vowels, while; the state q is associated with the output ‘$’ that
changes the vowels to ‘$’.
Q.28 Construct a DFA equivalent to the NFA: ({p, q, r, s}, {0, 1}, N, p, {q, s}), where N is as given
in the following table:
Q  0 1
p {q, r} {q}
*q {r} {q, r}
r {s} {p}
*s - {p}
Solution:

Q.29 Write short notes on:

(1) Deterministic finite automata
(2) Moore and Mealy machines
(3) Moore’s algorithm for FSM equivalence
(4) Relative powers of NFA and DFA
(5) Limitations of FSM
Solution:
(1) Deterministic finite automata – Refer to the section 2.4.
(2) Moore and Mealy machines – Refer to the section 2.10.
(3) Moore’s algorithm for FSM equivalence – Refer to the section 2.12.1.
(4) Relative powers of NFA and DFA – Refer to the section 2.6.
(5) Limitations of FSM – Refer to the section 2.14.
Q.30 Give formal definitions for the following:

(1) Deterministic finite automata
(2) NFA with -transitions
(3) Moore machine
(4) Acceptance of a string by FA
Solution:
(1) Deterministic finite automata – Refer to the section 2.4.
(2) NFA with -transitions – Refer to the section 2.7.
(3) Moore machine – Refer to the section 2.10.1.
(4) Acceptance of a string by FA – Refer to the section 2.3.3.
Q.31 Translate the following Mealy machine into its equivalent Moore machine.

Solution:
Q\ 0 1 Q\ 0 1
q1 q1 q2 q1 1 0
q2 q4 q4 q2 1 1
q3 q2 q3 q3 1 1
q4 q3 q1 q4 0 1
According to the rule of conversion, the resultant Moore machine consists of states,
Q' = Q x  = { [ q1, 0], [ q1, 1], [ q2, 0], [ q2, 1], [ q3, 0], [ q3, 1], [ q4, 0], [ q4, 1] }

a) '([q1, 0], 0) = [ (q1, 0),  (q1, 0)]
= [q1, 1]
'([q1, 0], 1) = [ (q1, 1),  (q1, 1)]
= [q2, 0]
'([q1, 0]) = 0
b) '([q1, 1], 0) = [ (q1, 1),  (q1, 1)]
= [q2, 0]
'([q1, 1], 1) = [ (q1, 1),  (q1, 1)]
= [q2, 0]
'([q1, 1]) = 1
c) '([q2, 0], 0) = [ (q2, 0),  (q2, 0)]
= [q4, 1]
'([q2, 0], 1) = [ (q2, 1),  (q2, 1)]
= [q4, 1]
'([q2, 0]) = 0

d) '([q2, 1], 0) = [ (q2, 0),  (q2, 0)]

= [q4, 1]
'([q2, 1], 1) = [ (q2, 1),  (q2, 1)]
= [q4, 1]
'([q2, 1]) = 1
e) '([q3, 0], 0) = [ (q3, 0),  (q3, 0)]
= [q2, 1]
'([q3, 0], 1) = [ (q3, 1),  (q3, 1)]
= [q3, 1]
'([q3, 0]) = 0
f) '([q3, 1], 0) = [ (q3, 0),  (q3, 0)]
= [q3, 1]
'([q3, 1], 1) = [ (q3, 1),  (q3, 1)]
= [q3, 1]
'([q3, 1]) = 1
g) '([q4, 0], 0) = [ (q4, 0),  (q4, 0)]
= [q3, 0]
'([q4, 0], 1) = [ (q4, 1),  (q4, 1)]
= [q4, 1]
'([q4, 0]) = 0
h) '([q4, 1], 0) = [ (q4, 0),  (q4, 0)]
= [q3, 0]
'([q4, 1], 1) = [ (q4, 1),  (q4, 1)]
= [q4, 1]
'([q4, 1]) = 1
Q.32 Convert the following NFA into NFA without -moves.

Figure 2.57: Example NFA with -moves
Solution:
Let's calculate - closure of the states.
-Closure (A) = {B, C}
-Closure (B) = {B}
-Closure (C) = {C}
-Closure (D) = {D}
As D is the only final state for given NFA without -transitions, F’: set of final states for resultant NFA
without -moves is given as,
F' = {D}
Now let us find transition function ' for the resultant NFA. This can be obtained by using rule:
' (q, a) = -closure ((^ (q, ), a))
' (A, 0) = -closure ((^ (A, ), 0))

= -closure (((B, C), 0))
= -closure ((B, 0) U (C, 0))
= -closure ({D}, {c})
= {C, D}
' (A, 1) = -closure ((^ (A, ), 1))
= -closure (((B, C), 0))
= -closure ((B, 1) U (C, 1))
= -closure ({B}, {D})
= {B, D}
' (B, 0) = -closure ((^ (B, ), 0))

= -closure ((B, 0))

= -closure ({D})
= {D}
' (B, 1) = -closure ((^ (B, ), 1))
= -closure ((B, 1))
= -closure ({B})
= {B}
' (C, 0) = -closure ((^ (C, ), 0))
= -closure ((C, 0))
= -closure ({C})
= {C}
' (C,1) = -closure ((^ (C, ), 1))
= -closure ((C, 1))
= -closure ({D})
= {D}
' (D,0) = -closure ((^ (D, ), 0))
= -closure ((D, 0))
= -closure ()
=
' (D,1) = -closure ((^ (D, ), 1))
= -closure ((D, 1))
= -closure ()
= 
From the above transitions, we can construct the transition table for the equivalent NFA without -moves
as below,
Q\∑ 0 1
A {C,D} {B,D}
B {D} {B}
C {C} {D}
D  

The transition graph for the NFA without -moves is,

TOC Reference

Uploaded by

Copyright:

Available Formats

TOC Reference

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

TOC Reference

Uploaded by

Copyright:

Available Formats

Theory of Computation Solutions for review questions

Author: Vivek Kulkarni

Chapter-2: Finite State Machines

Solutions for Review Questions

@ Oxford University Press 2013. All rights reserved. 1

Q.1 Construct Mealy and Moore machines for the following:

Q.2 Discuss the relative powers of NFA and DFA.

@ Oxford University Press 2013. All rights reserved. 2

Q.4 Prove the following:

Q.5 Define and give suitable examples for a transition graph.

Q.7 Explain whether a language of palindromes is accepted by an FSM. Justify.

@ Oxford University Press 2013. All rights reserved. 3

Q.8 Describe the following:

Q.9 Write a short note on Mealy and Moore machines.

Q.11 Write a short note on the properties and limitations of FSM.

Q.12 Compare Moore and Mealy machines.

@ Oxford University Press 2013. All rights reserved. 4

Figure 2.51: Example automata

@ Oxford University Press 2013. All rights reserved. 5

Figure 2.52: Example NFA with -transitions

@ Oxford University Press 2013. All rights reserved. 6

q0 {q2, q3, q5} {q4, q3, q5}

q1 {q2, q3, q5} {q4, q3, q5}

Figure 2.53: Example Mealy machine

@ Oxford University Press 2013. All rights reserved. 7

 : Q x   Q (State function)  : Q x    (Machine function)

@ Oxford University Press 2013. All rights reserved. 8

e) '([q3, z1], 0) = [ (q3, 0),  (q3, 0)]

Figure 2.54: Example DFA

@ Oxford University Press 2013. All rights reserved. 9

Q.22 Convert the following Mealy machine to a Moore machine.

Figure 2.55: Example Mealy machine

 : Q x   Q (State function)  : Q x    (Machine function)

@ Oxford University Press 2013. All rights reserved. 10

Also ' and ' can be found as follows:

1) Compute the -closure of each state

@ Oxford University Press 2013. All rights reserved. 11

1) -closure (p) = {p}

2) All the strings of length three or less accepted by the automata

@ Oxford University Press 2013. All rights reserved. 12

The reduced state DFA is,

@ Oxford University Press 2013. All rights reserved. 13

'(pq, 0) = [ (p, 0) ∪  (q, 0)] = [{p,q} ∪ {r}] = pqr

@ Oxford University Press 2013. All rights reserved. 14

(5) *pq pqr s

(6) *pr pqs 

(11) *pqr pqrs s

(12) *pqs pqrs s

(13) *prs pqs s

(15) *pqrs pqrs s

We also have relabelled the states from (1) to (15).

@ Oxford University Press 2013. All rights reserved. 15

@ Oxford University Press 2013. All rights reserved. 16

The TG for the DFA can be drawn as,

@ Oxford University Press 2013. All rights reserved. 17

The transition diagram for the mealy machine is as shown below,

@ Oxford University Press 2013. All rights reserved. 18

@ Oxford University Press 2013. All rights reserved. 19