My Youtube Video Channel ( With Theory of Computations)


Thursday, February 10, 2011

Difference between DFA and NFA


  • 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.

  • DFA can not use Empty String transition.
  • NFA can use Empty String transition.

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

  • 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.

1 comment: