10.
14.
23. (a) Yes
(b) No.
CHAPTER 3
12. Defining A
q q
a b z a b
q z q
f
= ({ , }, { , }, { , , }, , , , { }}
0
0
3
δ
δ is given by
δ
δ
δ
( , , ) {( ,
)}
( , , ) {( ,
)}
( , , ) {(
q a z
q az
q b z
q bz
q a a
q
0
0
0
0
=
=
=
, )}
( , , ) {( , )}
( , , ) {( , )}
( , , )
(
aa
q b b
q bb
q a b
q
q b a
q
δ
δ
δ
δ
=
=
∈ =
, , ) {( , )}
∈ =
∈
a
q f
A accepts the given set by final state.
14. M
q
S B
q S
=
∅
({ }, { , }, { , , , }, , , , }
01
01 δ
δ is defined as
δ
δ
δ
( , , ) {( ,
)}
( , , ) {( , ), ( , ), ( , )}
(
q S
q BB
q B
q S q s q
∈
=
∈
=
0
0
1
0
q
q
q
q
, , ) {( , )}
( , , ) {( , )}
0 0
11
=
∈
=
∈
δ
15. G
S a b P S
= ({ }, { , }, , )
P S
aSb S
aS S
a
:
,
,
→
→
→
A q a b S a b
q S
:({ }, { , }, { , , }, , , , )
δ
∅
where δ( , , ) {( ,
), ( , ), ( , )}
q S
q aSb q aS q a
∈
=
δ
δ
( , , )
( , , ) {( , )}
q a a
q b b
q
=
=
∈
316
Theory of Automata, Formal Languages and Computation
a
S
A
b
S
a
S
a
A
a
a
{,} qq 14
{} q 3
{} q 2
{} q 4
{} s 0
{} q 0
φ
a
b
a,b
a,b
a
a
b
b
a
b