What is the trade off in converting a DFA into a NFA?

Question

When a DFA is converted into an equivalent NFA, the NFA gives more convenience to many yes/no kind of problems (such as a word belong to a language or not?). I want to know in general at what price this convenience is achieved?

Answer 1

A deterministic finite state automaton (DFA) is in fact a non-deterministic finite automaton (NFA) where the transition function only maps to singelton sets.

Recall that from the first principles that the transition function, $\delta$, in a DFA is defined as $$ \delta: Q*E \rightarrow Q,$$ whereas for an NFA it is $$ \delta: Q*E \rightarrow \mathcal{P}(Q)$$

This means that you can (intuitively) think of a DFA as a "special type of" NFA.

Answer 2

It may be difficult to get an answer you like because given a DFA it is hard to find an equivalent NFA that has fewer states. If all you know is the DFA, you are going to have to work extremely hard to get any equivalent NFA other than the DFA itself.

Suppose, however, that you do have an equivalent NFA and DFA where the NFA is smaller than the DFA. (Perhaps because you had the NFA in the first place, and used the Rabin-Scott powerset construction algorithm to find the equivalent DFA.) Given an NFA over $M$ symbols with $N_{\mathrm{NFA}}$ states, and an equivalent DFA with $N_{\mathrm{DFA}}$ states, and $N_{\mathrm{NFA}} \leq N_{\mathrm{DFA}}$, the DFA will be cheaper to simulate than the NFA.

For the DFA the current state is an integer $j \in N_{\mathrm{DFA}}$. You keep a table with $M N_{\mathrm{DFA}}$ entries where the $i$ + $jM$^th entry in the table gives you the next-state transition from state $j$ on symbol $i$. The lookup is $O(1)$.

For the NFA the current state is a set $J \subseteq N_{\mathrm{NFA}}$, and is typically represented with an $N_{\mathrm{NFA}}$ bit vector. (A $1$ at position $j$ in the vector means that $j$ is a member of the current state.) Your state transition is much more expensive. For each element $j_k$ in the current state set you need to look up the (possibly $N_{\mathrm{NFA}}$ element) next state set, and then union together all the results of the lookups. Perhaps there is an algorithm for doing this faster than $O(N_{\mathrm{NFA}}^2)$, but I don't know it off hand.

There's a memoization based optimization that is typically performed during NFA simulation (you keep a cache that maps a hash of the current state and the current symbol to its next state, so that if you get that state/symbol pair again in the future you get the next state in $O(1)$), but this doesn't change the worst case bounds.

Answer 3

I assume you mean converting a DFA to a smaller NFA that actually uses the nondeterminism.

If your machine uses nondeterminism, it's more difficult to simulate in on a deterministic computer. You have to keep track of all possible computation states, since your computer can't "guess" the correct nondeterministic transition like the NFA would. This basically amounts to converting your NFA back to a DFA with (exponentially) more states.