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 slo开发者_JAVA技巧wer to arrive at the accept state than DFA's but are there any other explicit, well known advantages/disadvantages?

---

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

---

The advantage of NFA's over DFA's is the property, to always "choose the right path". Since you cannot say in an algorithm to "choose the right path", usually a conversion from NFA to DFA works, creating DFA states that symbolize multiple NFA states. Thus, when your NFA is in State A and has the choice to go to A,B or C then the next state in your DFA would be {A,B,C}.

This explains the advantages and the disadvantages: DFA's can be implemented easier since their next state is determined by a function. NFA's allow a user to easier express what they want, because the NFA can choose between many path's.

---

One definite advantage of NFA's over DFA's is that, you can build a FA representing the language that is a union, intersection, concetanation etc. of two (or more) languages easily by using NFA's. That is to say, if you have slightly simple FA's doing parts of the job, you can combine them easily using NFA's. While using a DFA, you need to build a new automata doing all the job by itself.

see, it is easier to implement. but there's the time issue as you mentioned.