Showing posts from February 6, 2011

Relationship between DFA and NFA

Relationship between DFA and NFA
DFA is a kind of NFA But reverse is not True.
DFA and NFA have same capabilities.(Every Language that can be recognized by a DFA can also be recognized by a NFA. The reverse is True.)
It will be more easy to design NFA than DFA.Both DFA and NFA can only have one start state.But they can have multiple Final state.

Difference between DFA and NFA

(1) For Every symbol of the alphabet, there is only one state transition in DFA.We do not need to specify how does the NFA react according to some symbol.

(2) DFA can not use Empty String transition.NFA can use Empty String transition.

(3) DFA can be understood as one machine.NFA can be understood as multiple little machines computing at the same time.

(4) DFA will reject the string if it end at other than accepting state.If all of the branches of NFA dies or rejects the string, we can say that NFA reject the string.