Ì Exam ple 1.2.9: Determine an NFA with three states that accepts the
language {ab, abc}
* .
Solu tion:
NFA for the language
L ab abc
= { ,
}
*
should be such that it accepts “ab” or “abc” in the first step and then this is
looped with initial state so that any combination of “ab” and “abc” can be
accepted.
Hence we have the NFA as
M
q q q
a b c
q q
= ({ , , }, { , , }, , , { })
0
1
2
0
1
δ
which is shown below:
Ì Exam ple 1.2.10: Determine an NFA that accepts the language
L aa a b
(
(
))
*
+ .
Solu tion:
NFA is given by
M
q q q
a b
q q
= ({ , , }, { , }, , , { })
0
1
2
0
2
δ
1.3 EQUIVALENCE OF NFA AND DFA
Def i ni tion
Two finite accepters M 1 and M 2 are equivalent iff
L M
L M
( )
(
)
1
2
=
i.e., if both accept the same language.
Both DFA and NFA recognize the same class of languages. It is important
to note that every NFA has an equivalent DFA.
Let us illustrate the conversion of NDA to DFA through an example.
DFA and NFA
75
q 0
q 1
q 2
a
b
a
a
q 0
q 1
a,b
a
q 2
a