(b)
14. For the finite-state machine shown in problem (13), determine the
output for each of the following input strings
(a) 0111
(b) 11011011
(c) 01010101010
15. Construct a finite-state machine that delays an input string two bits,
giving 00 as the first two bits of output.
16. Construct a finite state machine that determines whether the input string
has a 1 in the last position and a 0 in the third to the last position read so
far.
17. Construct the state table for the Moore machine with the state diagram
shown below. Each input string to a Moore machine M produces an
output string. The output corresponding to an input string
a a
a k
1
2
, ,
,
KK
is the string g s g s
g s k
( ) ( )
( )
0
1 KK
where
s
f s
a
i a
i
1 =
−
(
, ) for i
k
= 1 2
, , KK .
18. Determine the output generated by the Moore machine shown in
problem (17), with each of the input strings shown below.
(a) 0101 (b) 111111 (c) 11101110111
19. Construct a Moore machine that determines whether an input string
contains an even or odd number of 1
s
. The machine should give 1 as
output if an even number of 1
s are in the string and 0 as output if an odd
number of 1
s are in the string.
20. Obtain the languages recognized by each of the following Finite-state
automata shown below.
DFA and NFA
103
s 0
s 1
s 2
Start
1
0
0
1
1
0
1
0
s 0
s 1
s 2
Start
1,1
0,1
1,0
0,0
0,0
1,0