5. L
n
n n
n
=
≥
{ ,
,
}
0 0 010 11
0
6. M
q
q
q
q q
q q
q q
q
1
0
1
2
0
1
0
2
1
2
0
= ∅
({[ ], [ ], [ ], [ ], [ , ], [ , ], [ , ]
[ , , ]}, { , }, , [ ], {[ ], [ , ],
[ , ], [ ,
q q
a b
q
q
q q
q q
q q
1
2
0
1
0
1
1
2
0
′
δ
1
2
, ]}
q
which is the DFA of the form ′ = ′
′ ′ ′
M
Q
q F
( , , , , )
Σ δ 0
with δ′ given by
the table below.
a
b
[∅]
[∅]
[∅]
[q 0 ]
[q 1 , q 2 ]
[∅]
[q 1 ]
[∅]
[q 2 ]
[q 2 ]
[∅]
[q 2 ]
[q 0 , q 1 ]
[q 1 , q 2 ]
[q 2 ]
[q 0 , q 2 ]
[q 1 , q 2 ]
[q 2 ]
[q 1 , q 2 ]
[∅]
[q 2 ]
[q 0 , q 1 , q 2 ]
[q 1 , q 2 ]
[q 2 ]
7.
8.
9. (a) b aa ab a
*
*
*
Answers to Exercises
309
q 0
q 1
q 2
a
q 3
a
b
a
q 4
q 5
b
b
a
b
q 4
q 3
b
b
a,b
a
a
a