Solu tion
The given language L b ab m n
m
n
=
>
{
: ,
}
0 has all words with exactly one ‘a’
which is neither the first nor last letter of the word i.e., there is one or more b’s
before or after ‘a’.
DFA is drawn above for the automaton M,
where M
Q
q F
= ( , , , , )
Σ δ 0
with
Q q q q q q
= { , , , , }
0
1
2
3
4
Σ = { , }
a b ; q 0 = Initial state,
F = {q 3 } = Final state.
and
δ is defined as per the language L. (q 4 is “dead” state)
Ì Exam ple 1.1.8: Given Σ = { , }
a b , construct a DFA which recognize the
language L a b m n
m n
=
>
{
: ,
}
0 .
Solu tion
The given language L a b m n
m n
=
>
{
: ,
}
0 has all words which begin with one or
more a’s followed by one or more b’s.
The finite automaton M Q
q F
( , , , , )
Σ δ 0
is with
Q = {q 0 , q 1 , q 2 , q 3 }
Σ = {a, b}
q 0 = Ini tial state
F = {q 2 } = Final state
and
δ as defined by language L.
The DFA is as shown below.
Here q 3 is a “dead” state.
64
Theory of Automata, Formal Languages and Computation
q 0
q 1
q 2
q 3
q 4
a
b
b
a,b
a
a
a
b
q 0
q 1
q 2
q 3
a
b
a,b
a
a
b
b