Comparison between DFA and NFA | Equivalence of DFA and NFA
Sr No
|
DFA
|
NFA
|
01
|
The
transition from a state is to a single next state for each input symbol. Hence
it is called DFA
|
The
transition from a state is to a single next state for each input symbol. Hence
it is called DFA
|
02
|
Empty
string transitions are not seen in DFA
|
NDFA
permits empty string transitions
|
03
|
Backtracking
is allowed in DFA
|
In
NDFA, backtracking is not always possible
|
04
|
Requires
more space
|
Requires
less space
|
05
|
A
string is accepted by DFA , if it transits to a final state
|
A
string is accepted by NFA, if at least one of all possible transitions ends
in a final state
|
06
|
DFA
will reject the string, if it ends at other than accepting state.
|
If
all of the branches of NFA dies or rejects the string, we can say that NFA
rejects the string
|
07
|
DFA
can be considered as one machine
|
NFA
can be considered as multiple little machines computing at the same time
|
08
|
DFA
is very difficult to design
|
NFA
is easier to design
|
09
|
The
transition function δ is
δ: Q x ∑
à
Q
|
The
transition function δ is
δ: Q x ∑
à
2Q
|
Comments
Post a Comment