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.
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 as,
optionally followed by either bab or bb;
as a regular expression,
that’s a*(ba?b)?.
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.
Looking for comments…