Advantages/Disadvantages of NFA over DFA and vice versa
What are the relative pro's and con's of both DFA's and NFA's when compared to each other?
I know that DFA's are easier to implement than NFA's and that NFA's are slower to arrive at the accept state than DFA's but are there any other explicit, well known advantages/disadvantages?
Answer
NFAs and DFAs accept the same set of languages - the regular languages.
A direct implementation of an NFA (which is not a DFA, since DFA is a subset of NFA) usually involves allowing backtracking whereas a direct implementation of a DFA requires only as many steps as the input length, so in that sense, DFAs "arrive at the answer" faster than equivalent NFAs (which are not DFAs).
When trying to find a FA corresponding to a given language or RE (e.g., by an algorithm), it is usually easier to arrive first at the NFA (since the rules are less strict). This is especially true when attempting to demonstrate the existence of a FA, since the existence of an NFA is as good as the existence of a DFA. If a DFA is needed, algorithms exist for (a) converting the NFA to an equivalent DFA and (b) minimizing the DFA.
Making gross generalizations, DFAs are faster but more complex (in terms of number of states and transitions) whereas NFAs are slower but more simple (in the same terms).