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?
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.
In theory, all NFAs have equivalent DFAs. In practice, extra information encoded in the model (outside of formal language/finite automata theory) such as annotations on states may mean that some NFAs have no equivalent DFAs - they are inherently nondeterministic. In my experience, eliminating all non-determinism that can be eliminated (with a variant of the subset construction), combined with some extra cleanups and minimization, still seems sufficient to give canonical forms, though I never formally proved that.
Also, there is no unique minimal equivalent automata - only a unique equivalent deterministic automata (or as-deterministic-as-possible with state annotations). 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 (the "partial derivatives of regular expressions" approach is one, though I'm not that familiar with these myself - derivatives of regular expressions (without the "partial" are an earlier method for not-necessarily-minimal DFAs).
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".
https://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 that 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.
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.
/\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.