Ì Exam ple 1.1.14: Determine the languages produced by the FA shown
in Figs. (a) and (b).
Solu tion
(a) For Σ = { , }
a b , language generated = {a,b}
*
(∈ will be accepted when initial state equal final state).
(b) For Σ = { , }
a b , language generated = {a, b}
+
{∈ is not accepted).
Ì Exam ple 1.1.15: Determine the FA if Σ = { , }
a b for
(a) Language generated L
ab
ab n
A
n
=
=
≥
( )
{( ) |
}
*
0
(∈-not accepted)
(b) Language generated L
ab n
B
n
=
≥
{( ) |
}
1
(∈-not accepted)
Solu tion
(a) Given L
ab n
A
n
=
≥
{( ) |
}
0 .
The FA is shown below in Fig. (a).
The FA is given by
M q q q
a b
q q
({ , , }, { , }, , , )
0
1
2
0
0
δ
where q 2 is a “dead state”.
68
Theory of Automata, Formal Languages and Computation
q 2
q 0
q 1
a
b
a
b
a
b
Fig. (a)
q 1
a
b
q 0
a
b
(b)
q 1 a
b
(a)