Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
    
The big advantage of NFAs is that they can search much faster; the big advantage of DFAs is that they are physically possible. Or were you referring to some sort of implementation? –  David Thornley May 11 '11 at 19:41
    
NFAs aren't necessarily slower. The logic to execute them is a tad more complex, but the large number of states for an equivalent DFA can mean that memory bandwidth becomes an issue. Organising a state table to optimise locality of accesses is, I expect, very difficult. So the slightly more complex code for NFAs is a trade-off against memory usage which may well pay off with faster run-times, at least in principle, though I've not looked up any real-world benchmarks. –  Steve314 May 11 '11 at 22:03
1  
This sounds like a question for CSTheory.stackexchange.com –  Jonas May 11 '11 at 22:44
add comment

3 Answers

Nondeterministic automata can have far fewer states, but the engine to evaluate them must be capable of being in multiple states at once - all possible states. This can lead to a trade-off between memory requirements and code complexity when executing the automaton.

Personally, though, I think the more interesting issues relate to how you manipulate the automata themselves.

A DFA can be considered a special-case NFA - IOW you can define NFA to mean potentially (but not necessarily) non-deterministic.

Even with DFA, there are many possible equivalent automata that will give the same behaviour. But there is only one minimal DFA with that behaviour. This gives a canonical form for both a family of DFAs and for a (much larger) set of NFAs. But even when defining the canonical form for all equivalent NFAs, you must use a minimal canonical deterministic automaton.

In coding terms, there is more to defining a canonical DFA than just minimisation - you also need a canonical representation. However, using normal minimisation algorithms, these issues tend to resolve themselves in my experience, basically because the minimisation code is deterministic itself.

Once you have a canonical form of an automaton, you can derive a hash, or can do ordered comparisons - you can use automata as keys into data structures.

Some NFAs have no equivalent DFAs - they are inherently nondeterministic. Also, there is no unique minimal equivalent automata - only a unique equivalent deterministic automata. An equivalent NFA to that minimal DFA may well be much smaller, but there is not (in general) one unique smallest equivalent NFA.

So working with DFAs is tempting because there is always one well-defined canonical result. If your goal is small automata, it's nice to have a clear definition of "smallest" and to always know that you're achieving it.

Using NFAs, you lose that nice "this-is-the-one-best-result" feeling. You have to make do with "small" rather than "smallest". You may get different automata where you expect equivalent results, and not be confident that they are in fact equivalent. But a typical "small" NFA may be much smaller than its "smallest" equivalent DFA, so that superlative may well be a red herring.

I think of it a bit like approximation algorithms. Do I need the "perfect" result? Though in this case, the NFA result is still (in behaviour terms) perfect. Only the representation loses the "perfect" label, and even then, labelling the minimal DFA as "perfect" only works because you're ignoring the potentially better NFA representations.

Anyway, when working with NFAs, the choice of representations for the results is basically heuristic. There are obviously well know methods for manipulating NFAs (IIRC the "derivatives of regular expressions" approach is one, though I'm not that familiar with these myself).

DFAs are tempting because you can avoid that subjective grey-area. But I'm quite confident that this temptation should be treated with suspicion - because I fell into this trap myself :-(

In fairness, the DFAs I deal with aren't that big. But having a few thousand states where intuitively I was expecting a few dozen happens a lot - and that doesn't count all the states generated and discarded for intermediate results. I've survived this relatively unscathed, but with much more respect for the term "exponential growth".

share|improve this answer
add comment

http://swtch.com/~rsc/regexp/regexp1.html gives you a good overview of the differences between NFAs and DFAs, as well as concrete information for how to make DFAs do things that most people don't think that they can do (find the boundaries of subpatterns). The reason why most people don't know that is possible is because most programmers get their information from Jeffrey Friedl, who got the theory wrong in an otherwise wonderful book on regular expressions. (I recommend Mastering Regular Expressions because it is a good practical introduction to them, but the theory is not correct.)

If you want the simple version, NFAs are simpler to implement and allow you to implement more features, at the cost of having some pathological cases where they will take exponential time to figure out that there is no match. (In practice, won't match before the Sun blows up.) By contrast DFAs offer performance guarantees, but some pathological regular expressions can take an extremely large amount of memory to express as a DFA.

share|improve this answer
add comment

Its been a while since I took CS theory but I believe there's no functional difference between the two. Any language that can be defined in NFA can also be defined in DFA.

NFA is a bit more complex to implement but once implemented, creating graphs becomes easier for the end-user. In other words to define the same language using DFA, you would be required to define more states and transitions than when using NFA.

share|improve this answer
    
This is wrong. NFAs can implement backreferences. DFAs cannot. Therefore anything whose regular expressions are "Perl compatible" can't be implemented with a DFA. –  btilly May 11 '11 at 19:44
    
if you are 100% sure that you are correct, you might want to update the wikipedia. I had to look it up since you called me on it. this is what the wiki says "Although the DFA and NFA have distinct definitions, it may be shown in the formal theory that they are equivalent, in that, for any given NFA, one may construct an equivalent DFA, and vice-versa". And hey, I do remember something from CS theory from 10 years ago :) –  DXM May 11 '11 at 19:46
3  
@btilly: No sort of FA implements backreferences. A DFA can be constructed from an NFA by taking the power set of the NFA's states for the DFA's states, so an NFA can do nothing a DFA cannot. You may be thinking of some particular implementation with something called an NFA with some extensions. –  David Thornley May 11 '11 at 19:55
    
@DXM, @david-thornley: In the real world when people talk about NFAs they use the term differently from CS theory, ditto "regular expression". In particular part of the state can be backreferences to previous parts of the string, which is easy to implement but gives infinite possibilities. For example /\b(\w+)\s+\1\b/ is a regular expression for finding doubled words that most modern regular expression engines will accept. It is not truly regular. And the regular expression engines, though everyone calls them NFAs, are not truly NFAs. –  btilly May 11 '11 at 19:59
    
@btilly: Some people use the term differently from CS theory; you've run into two who don't. I actually don't remember anybody referring to "regular expression" engines (since they do things even a context-free grammar can't) as NFAs, and I'm something of a Perl fan. The fact that the question is tagged "compilers" and "finite-state-machine" suggests to me that this might be a CS theory question. Which is why I voted to close as "not a real question" - when two contributors who know what they're talking about disagree on an objective point, it's time to close. –  David Thornley May 11 '11 at 20:59
show 6 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.