-1
$\begingroup$

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?

$\endgroup$
  • 5
    $\begingroup$ A "DFA is a NFA ".. recall from the first principles, in DFA is $$\delta:Q*E \rightarrow Q$$ whereas the NFA has $$\delta:Q*E \rightarrow \mathcal{P}(Q)$$ so you can (intuitively) think of DFA as a 'special type of' NFA. $\endgroup$ – Subhayan Sep 3 '13 at 12:14
  • $\begingroup$ @Subhayan You should make this into an answer. $\endgroup$ – Pål GD Sep 3 '13 at 12:28
  • 2
    $\begingroup$ I wonder which problems you are referring to. $\endgroup$ – Raphael Sep 3 '13 at 12:29
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is not precisely what I am looking for. Can you please read my question again. $\endgroup$ – gpuguy Sep 3 '13 at 12:55
  • 1
    $\begingroup$ @gpuguy – Subhayan answered this perfectly. There is no price for this "convenience". An NFA allows for the transition function to map to sets of arbitrary sizes whereas a DFA maps to sets of size one. You could ask "which convenience do a DFA have over a NFA?", to which the answer would be that it only maps to single states and not sets of states. $\endgroup$ – Pål GD Sep 3 '13 at 12:56
4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.