Case (ii): b a n
n : ≥1
q 0 goes to a state q 1 where all b’s are accepted and when an ‘a’ is
encountered it goes to final state q 2 . An additional state q 4 is added as a
rejection state for the cases when ‘b’ is encountered after a’s of case (i) or when
‘a’ or ‘b’ is encountered after b
n a of case (ii).
The NFA is given by
M
q q q q q
a b
q q q
= ({ , , , , }, { , }, , , { , })
0
1
2
3
4
0
2
3
δ
which is shown in the fig. below.
Ì Exam ple 1.2.8: Design an NFA with no more than five states for the set
{
:
} {
:
}
abab n
aba n
n
n
≥ ∪
≥
0
0 .
Solu tion
NFA for the language
L abab n
aba n
n
n
=
≥ ∪
≥
{
:
} {
:
}
0
0
is
M
q q q q q
a b
q q q q
= ({ , , , , }, { , }, , , { , , })
0
1
2
3
4
0
2
3
4
δ
.
Here the NFA is such that it accepts all strings of the type aba
n and abab
n
where n ≥ 0.
q 2 is for the case when string is ab, i.e. ab
n with n = 0.
q 3 is for the case when string is abab
n with n ≥ 0.
q 4 is for the case when string is aba
n with n ≥ 0
This NFA is shown in the fig. above.
74
Theory of Automata, Formal Languages and Computation
π
q 0
q 2
q 3
a
b
b
a
q 1
q 4
a
a