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

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

<p>I know that is possible to <em>convert</em> 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.</p>

<p>Anyway, does it make <strong>any</strong> 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?</p>

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.