Thursday, February 10, 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




DFA Vs. 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.