Nondeterminism in Finite State Machines

Yesterday, I started to explain the difference between a non-deterministic FSM, and a deterministic one. Today I'm going to expand on that theme a bit.

From any given state, a deterministic automaton has no more than one possible transition for each input symbol. A non-deterministic machine doesn't have that restriction: it can have as many transitions as it wants for any pair of (state,symbol). In NFAs, we often even add a convenient shorthand called an empty transition - that is, a free transition from one state to another which the NFA can take if it wants to, without consuming an input symbol. We typically label empty transitions with a greek letter epsilon or a lower-case e.

That's actually the general difference between deterministic machines, and non-deterministic ones. Deterministic machines have exactly one thing they can do in any situation; non-deterministic ones have multiple choices.

But - what does that actually mean in terms of computation?

Well, for both deterministic and non-deterministic FSMs, they accepts a string as a member of their language if, after processing all of their input, they can end in a final state. For a deterministic machine, that's a straightforward notion: there is only one possible path through the FSM for any given input, and so there is exactly one possible state that the machine is in after processing the input.

For a non-deterministic machine, it's a bit more subtle. There can be many possible paths through the machine for a given input. We say that the machine traverses allof those simultaneously. So the DFAs computational path is a simple chain - a linear sequence of states that it passes through as it processes the input. The NFAs computation path is a tree - at any point where the NFA can take more than one transition for a given input symbol, the execution path branches, and it follows both.

Now, the obvious question is: what does this gain us? Can we do anything with an NFA that we can't do with a DFA?

Nope. Not a darn thing. For any NFA, there's a DFA that can compute exactly the same language. In fact, it's even a easy process to translate an NFA to a DFA. And there's no time-complexity difference: both NFAs and DFAs always take one step per input symbol. The only difference is space: translating an NFA to a DFA can result in a DFA with an exponetially larger set of states.

In fact the translation is specifically based on an exponential: given an NFA N, you can translated it into a DFA D, where the set of states in the DFA are isomorphic to the powerset of the states of N. (The powerset of a set S is the set of all subsets of S.) Basically, you take the set of all subsets of states of the NFA; and starting at the initial state, for each symbol, you figure out the set of states that you could transition to for that symbol, and in the DFA, you put a transition to the state corresponding to that set of states. Then you repeat that for each of the new states you added; and keep going until you stop adding states. In the worst case, for an N state NFA, you'll wind up with a 2^N state DFA.

Here's a fairly trivial example. Let's look at the language: (a+)|(ab*(a|b)) - that is, a language consisting of either a non-empty sequence of "a"s; or a single a followed by a (possibly empty) sequence of bs, followed by either a single a or b.



We can translate it into a DFA like the following:



The NFA is a lot easier to read; and this is a really trivial language. For anything more complicated, it gets a heck of a lot messier.

As a final note, non-determinism isn't always useless: for FSMs, you don't get additional power by using non-determinism. But for more advanced automatons, non-determinism might make a difference. It definitely can make a space difference for algorithms on turing machines. Does it make a time difference? We don't know.