Ì Exam ple 1.2.6: Given L is the language accepted by NFA in Fig.
Determine an NFA that accepts L
a
∪ { }.
5
Solu tion
The language accepted by the given NFA is
L a
a n
n
=
∪
{ } { :
3
is odd}.
Now to make an NFA accepting the language:
L a
a n
n
=
∪
∪
{ } { :
}
3
is odd} {a
5 .
This is accomplished by adding two states after state q 3 viz., q 6 and q 7 as shown
in fig.
The NFA is given by
M
q q q q q q q q
a
q q q q
= ({ , , , , , , , }, { }, , , { , , })
0
1
2
3
4
5
6
7
0
3
5
7
δ
Ì Exam ple 1.2.7: Find an NFA with four states for
L a n
b a n
n
n
=
≥ ∪
≥
{ :
} {
:
}
0
1
Solu tion
NFA for the language:
L a n
b a n
n
n
=
≥ ∪
≥
{ :
} {
:
}
0
1
For such a language two cases are to be considered.
Case (i): a n
n , ≥ 0
q 0 goes to a state q 3 where all a’s are absorbed. Hence a
n is accepted.
DFA and NFA
73
q 0
q 1
q 2
q 3
a
a
a
q 4
q 5
a
a
a