Nondeterministic Automata
other posts

theory

Of NFAs and the unimportance of regular nondeterminism

In previous posts I discussed nondeterminism, where a machine makes every choice at the same time and discards those that don’t work; and state machines, in particular Deterministic Finite Automata. We now put those two together to introduce Nondeterministic Finite Automata, or NFAs.

# NFAs

An NFA is machine that can be in several different states. It reads a sequence of symbols from some alphabet and, for each symbol, transitions to a different state. And, because they are nondeterministic, they can transition to as many or few states as there happen to be.

Consider the following example:

In this example, the machine starts in state 1, and stays there when it reads an `a`. When it reads a `b` it transitions to both states 2 and 3, nondeterministically. If it read another `b`, the version of the universe where it chose state 3 would vanish, since we can’t read a `b` from state 3, and the version where we chose state 2 would transition to state 4. If it read anything after that, the sole remaining version of the universe would vanish and the machine would reply “‍no‍”.

The language of a machine is the set of sequences it accepts. For this example, the language is any number of `a`s, optionally followed by either `bab` or `bb`; as a regular expression, that’s `a*(ba?b)?`.

# NFA = DFA

Any deterministic finite automata (DFA) is also an NFA. Any NFA can be turned into a DFA that accepts the same language. Hence, NFAs and DFAs are interchangable.

To build a DFA for an NFA, we start by DFA state for every set of NFA states; hence, if the NFA has states 1, 2, 3, and 4 then the DFA will have states {}, {1}, {2}, {3}, {4}, {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}, {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}, and {1,2,3,4}. We mark a DFA state accepting if any of its element NFA states is accepting. The edges of the DFA are pulled from the NFA.

Converting our example NFA to a DFA and ignoring those DFA states that have no incoming edges we get:

A similar process can change any NFA into a DFA. For finite automata, all nondeterminism gives us is a more compact was of writing down some machines. Some other kinds of machines are more powerful when nondeterministic, meaning they can compute more things or do so more quickly; for finite automata, however, this is not the case.