Theory of Computation basics


#1

What are the fundamental differences between NFA and DFA?


#2

NFA or Non Deterministic Finite Automaton is the one in which there exists many paths for a specific input from current state to next state.

Deterministic Finite Automaton is a FA in which there is only one path for a specific input from current state to next state. There is a unique transition on each input symbol.

Note:

  • All DFA’s are by default NFA
  • All NFA’s are not DFA
  • Any given NFA can be converted to DFA
  • Both DFA & NFA are equivalent in power

#3

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