16.
17.
State
f
Input
0
1
g
s 0
s 1
s 2
1
s 1
s 1
s 0
1
s 2
s 1
s 2
0
18. (a) 11111 (b) 1000000 (c) 100011001100
19.
20. (a) L
n
a
n
=
=
{ |
, , ,
}
1
0 1 2 KK
(b) L b = { , }
1 01
(c) L
x n
x
c
n n
=
=
{ ,
|
, , ,
0 0 10
0 1 2 K and is any string}
21.
Answers to Exercises
311
s 3
s 1
s 2
s 4
s 0
0,0
0,0
1,0
0,0
Start
0,0
1,1
s 3
s 4
1,0
s 5
s 6
1,0
0,0
0,0
1,1
0,0
1,0
1,0
s 0
s 1
s 2
Start
0
1
1
0
0
0
s 3
1
0
1
1
1
0
s 0
s 1
Start
1
0
0
s 3
s 2
1
1
0
0
0,1
1
1
0