Can we say DFA is more efficient than NFA?

I just started reading about theory of computation. If we compare which is more powerful (in accepting strings), both are same. But what about efficiency ? DFA will be fast compared to NFA, since it has only one outgoing edge & there will be no ambiguity. But in case of NFA we have to check all possible cases & that surely takes time. So can we say DFA is more efficient than NFA ?

But, my other part of brain is also thinking that NFA exists only in theory, so we cannot compare it's efficiency with DFA.

-

migrated from cstheory.stackexchange.comFeb 1 '13 at 15:42

This question came from our site for theoretical computer scientists and researchers in related fields.

There are two answers, depending on how you define efficient.

Compactness of representation

Telling more with less: NFAs are more efficient.

Converting a DFA to an NFA is straightforward and does not increase the size of the representation.

However, there are regular languages for which the smallest DFA is exponentially bigger than the smallest NFA. A typical example is $(a|b)^*b(a|b)^k$ for $k$ fixed.

Computation

Running it fast: DFAs are more efficient.

The computers we use today are deterministic in nature. That makes them bad at dealing with non-determinism. There are two common ways of dealing deterministically with NFAs: backtracking on one side, which is rather costly, or keeping track of the active states, which means each transition will take up to $N$ times longer (where $N$ is the size of the NFA).

-
Regarding compactness, NFA's are not always more efficient! It's true that there are languages for which the minimal DFA is exponentially larger than the most compact NFA but what's the fraction of such languages in the set of all languages? – saadtaame Feb 1 '13 at 16:39
@saadtaame It may seem weird, but in the strictest sense, NFAs don't have to be non-deterministic. DFAs are a special kind of NFA, i.e. NFAs with a singleton as starting set and the transition function is such that only one state is active at any given time. – Khaur Feb 1 '13 at 16:45
-1 "increasing its size (potentially a lot)". Simulating sets of NFA states by keeping a linked-list costs space at most $O(N)$ in the number of NFA states. The equivalent DFA, on the other hand, might have $O(2^N)$ states. – Wandering Logic May 11 '13 at 14:30
@WanderingLogic You're right, the conversion doesn't have to be explicit (you're still using the equivalent DFA, just not in extensive form). However the main point still stands, since this requires $O(N)$ times more computation time than running a DFA of the same size. I'll correct the last paragraph to account for that. – Khaur May 16 '13 at 15:50

In terms of power, they are equivalent as you said and there is an algorithm (subset construction) for converting an NFA to an equivalent DFA. As you might tell from the algorithm's name, it constructs subsets of states of the NFA. If your NFA has $n$ states, the algorithm may output a DFA with $2^n$ states but that's an upper bound. Sometimes, the number of states does not change at all or even reduces. So in practice, it matters less as to which one to use.

DFA matching is linear in the size of the input string. NFA matching involves backtracking so NFAs do more work. Thus, DFAs are more efficient.

-
But can we say DFA is more efficient ? – avi Feb 1 '13 at 16:16
@avi I edited the question! And by the way, NFA's do not exist in theory only: check this: swtch.com/~rsc/regexp/regexp1.html – saadtaame Feb 1 '13 at 16:23
@avi The problem here is that the DFA which is equivalent to the NFA will (often) be much larger. So even though you can check the DFA much quicker, you'll usually have to check a larger DFA. – Peter Feb 1 '13 at 16:28
@Peter, that the DFA is larger doesn't matter: It just means that the array giving the transition function is larger. – vonbrand Feb 1 '13 at 16:31
@Khaur, true. But if you get into that kind of problem, you have a humongous DFA. – vonbrand Feb 1 '13 at 17:17

NFAs can be computationally more efficient than DFAs, in the sense that they can be simulated on a parallel processor.

BTW: I see people saying that NFAs can't exist in reality. I beg to differ. A computer with a large number of processors can run many tasks in parallel and can be considered as a nondeterministic machine. One could assign each branch of computation to a new processor and halt them all whenever one of them accepts.

-

If you use the purely theoretical "number of steps to accept/reject" measure, a DFA will always be cheaper than an NFA that uses $\epsilon$-transitions. For more complex automata such a measure will make a difference.

-
Who said you have to use $\epsilon$-transitions? – Khaur Feb 1 '13 at 16:44
@Khaur, nobody did. Just added for completeness (I know you can get rid of just $\epsilon$-transitions in an NFA). – vonbrand Feb 1 '13 at 17:19
but aren't DFA free from ϵ-transitions ? – avi Feb 2 '13 at 3:57
@avi, yes. Feel free to edit the answer if it isn't clear there. – vonbrand Feb 2 '13 at 4:00
no, I am asking you. I am not sure about it either – avi Feb 2 '13 at 4:07

As others have noted, you have to define what "efficiency" means. In order to illustrate this, I give a reasonable model with a different answer.

Looking only at the automaton model(s), that is ignoring in particular how you would implement them on real machines, the obvious efficiency measure is "number of transitions taken on a (shortest) accepting run".

With respect to this measure, both automata models are equivalent, since both take exactly one transition per input symbol (w.l.o.g. we don't have $\varepsilon$-transitions). Note that the size of the considered automata does not factor in here.

-

Technically speaking a NFA is a more general concept then a DFA, since it is not required to use the nondeterminism. In other words: every DFA is a NFA. From this perspective there is for every language a NFA that is at least as efficient as the most efficient DFA, for whatever efficiency measure you favor.

Other than this I agree with Raphael that it depends very much what you mean with efficiency and on the implementation.

-