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.

9 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
  5. if there is no transition for a particular input from a state ,is it NFA or it is DFA ..
    if s1 is present state and for a it goes to s2 but no transition mentioned for b , then??

    ReplyDelete
    Replies
    1. If any transition for given alphabet is missing then its a NFA.
      In your case its a NFA

      Delete