Non-deterministic finite state machines in software development?

Question

Recently I've been thinking about finite state machines (FSMs), and how I would implement them in software (programming language doesn't matter).

My understanding is that deterministic state machines are in widespread use (parses/lexers, compilers and so on), but what's the matter with non-deterministic state machines?

I know that is possible to convert all non-deterministic state machines to deterministic ones (even programmatically). That's not my point. I also imagine that non-deterministic state machines are much more complicated to implement.

Anyway, does it make any sense to implement a non-deterministic state machine? Are there any special applications I don't know about? What could be the reasons to do that? Maybe optimized and specialized non-deterministic state machines are faster?

Answer 1

Most regular expression engines use non-deterministic automata since they offer much greater flexibility. DFAs are much more restricted. Have a look at some implementations and you'll see this. Microsoft even underlines this fact in their documentation of the .NET Regex class:

The .NET Framework regular expression engine is a backtracking regular expression matcher that incorporates a traditional Nondeterministic Finite Automaton (NFA) engine such as that used by Perl, Python, Emacs, and Tcl.

Matching behavior (first paragraph) – this article also offers a rationale for the employment of an NFA rather than the more efficient DFA.

Answer 2

As you know, NFAs and DFAs are computationally equivalent. It's one of the first theorems in automata theory. There are algorithms to convert one to another(unlike Pushdown or turing machines).

So. Why one over the other? Because representation of a given problem with a NFA is far easier than the equivalent DFA.

edit: in terms of actually computing the machine, DFAs are going to go faster because they don't have to backtrack. But they will take more memory to represent. (Mem vs CPU tradeoff)