Chapter 3: The Theory of Automata ~ 105
3.8 Construct a DFA equivalent to the NDFA described by Fig. 3.8.
3.9 M = ({qb q2' q3}, {O, I}, 8, ql' {q3}) is a nondeterministic finite
automaton. where 0 is given by
o(Qj. 0) = {q2' q3},
o(qj, 1) = {qd
O(q2> 0) = {qlo Q2},
O(Q2' 1) = 0
O(q3' 0) = {Q2},
O(Q3' 1) = {Q1' CJ2}
Construct an equivalent DFA.
3.10 Construct a transition system which can accept strings over the alphabet
a, b. .., containing either cat or rat.
3.11 Construct a Mealy machine which is equivalent to the Moore machine
defined by Table 3.33.
TABLE 3.33 Moore Machine of Exercise 3.11
Present state
a = 0
Next state
a = 1
Output
1
o
3.12 Construct a Moore machine equivalent to the Mealy machine M defined
by Table 3.34.
TABLE 3.34 Mealy Machine of Exercise 3.12
Present state
Next state
a = 0
a =
state
output
state
output
-'7q1
q,
q2
0
q2
q4
q4
1
q3
q2
q3
1
q4
q3
0
q,
1
3.13 Construct a Mealy machine which can output EVEN, ODD according
as the total number of l' s encountered is even or odd. The input
symbols are 0 and 1.
3J 4 Construct a minimum state automaton equivalent to a given automaton
M \vhose transition table is defined by Table 3.35.