13
$\begingroup$

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.

Improve this question
$\endgroup$
16
$\begingroup$

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).

Improve this answer
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – mrk Feb 1 '13 at 16:39
  • 2
    $\begingroup$ @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. $\endgroup$ – Khaur Feb 1 '13 at 16:45
  • 2
    $\begingroup$ -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. $\endgroup$ – Wandering Logic May 11 '13 at 14:30
  • $\begingroup$ @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. $\endgroup$ – Khaur May 16 '13 at 15:50
  • $\begingroup$ Thanks for this answer, because I've argued in my research that NFAs are better for evaluation and I see now that the point is more subtle. Overall, NFAs are definitely better for a fixed language, because any smart NFA evaluation algorithm will match the DFA evaluation complexity in the special case that the NFA is a DFA, and because the NFA may be more succinct. However, if the choice is between producing a highly-nondeterministic NFA or finding a clever way to get a DFA of the same size instead, for some particular application, DFA is better. $\endgroup$ – 6005 Jun 30 '18 at 18:04
4
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\begingroup$ But can we say DFA is more efficient ? $\endgroup$ – avi Feb 1 '13 at 16:16
  • 1
    $\begingroup$ @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 $\endgroup$ – mrk Feb 1 '13 at 16:23
  • $\begingroup$ @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. $\endgroup$ – Peter Feb 1 '13 at 16:28
  • $\begingroup$ @Peter, that the DFA is larger doesn't matter: It just means that the array giving the transition function is larger. $\endgroup$ – vonbrand Feb 1 '13 at 16:31
  • 1
    $\begingroup$ @Khaur, true. But if you get into that kind of problem, you have a humongous DFA. $\endgroup$ – vonbrand Feb 1 '13 at 17:17
2
$\begingroup$

Just adding to answers above:

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.

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ Neither DFAs nor NFAs exist in reality, both are just mathematical relations, and both can be simulated by algorithms. $\endgroup$ – jmite Jun 24 '16 at 21:48
1
$\begingroup$

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.

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

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
-4
$\begingroup$

As we know about Automata i.e machine which can perform any action without any man power or without direct participation of man. eg: washing machine. Finite Automata means we know the sate of performing task by machine like 1 press ON 2 press OFF so there is only 2 states i.e called finite automata. Now come to DFA i.e deterministic Finite automata. formally mean we can easily determine states there is no ambiguity and informally it need only 1 transition allowed on 1 symbol. NFA: non deterministic finite automata. there is need more time to compute actual state and there is ambiguity andd informally says there is multiple allowed transition on 1 symbol. in the case of time to reach the destination NFA takes more time than DFA but NFA can load more data than DFA. * DFA and NFA has same power to recognize the string. thank you.. Deepali kaushik

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ Finite automata have nothing whatsoever to do with washing machines. $\endgroup$ – David Richerby Jun 24 '16 at 12:22
  • 2
    $\begingroup$ @DavidRicherby. Perhaps the phrase "nothing whatsoever" is a bit strong. After all, we could say a washing machine has states ready, wash, rinse and spin with appropriate transitions between states. A better metaphor, though, would be a coin-operated soda vending machine. $\endgroup$ – Rick Decker Jun 24 '16 at 15:21
  • 1
    $\begingroup$ @RickDecker Agreed but spending time discussing the tiny relevance would be an example of what Wikipedia calls "undue weight". And, in any case, the part of the answer I'm talking about is discussing automata as self-powered machines, not computational devices. $\endgroup$ – David Richerby Jun 24 '16 at 16:28
  • 1
    $\begingroup$ I don't think this answer adds anything worthwhile towards the question. In particular, you are unclear about your measure of efficiency and seem to mix several concerns. $\endgroup$ – Raphael♦ Jun 26 '16 at 12:21
  • $\begingroup$ Tho other answers almost exhaust everything to be said and unfortunately your answer is slightly confusing. $\endgroup$ – Evil Jun 27 '16 at 1:18

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.