Thursday, February 10, 2011

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.

7 comments:

  1. can we have multiple accepting states in DFA?

    ReplyDelete
    Replies
    1. yes there is possibilityb to have multiple accepting states

      Delete
  2. Yes its Possible when One DFA is accepting two types of language.
    Example : Language Ends with aa or bb.

    ReplyDelete
  3. what is meant by language ?
    can u explain with an example sir ?
    please

    ReplyDelete
  4. In TOC
    Language (L) = Set of String = {a,aa,ba,aaa,aba,...}
    All Strings ends with a over set of character {a,b}

    ReplyDelete