Can we say DFA is more efficient than NFA? - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-18T15:06:24Z https://cs.stackexchange.com/feeds/question/9389 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/9389 13 Can we say DFA is more efficient than NFA? avi https://cs.stackexchange.com/users/6665 2013-02-01T14:42:41Z 2016-06-24T10:35:38Z <p>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 &amp; there will be no ambiguity. But in case of NFA we have to check all possible cases &amp; that surely takes time. So can we say DFA is more efficient than NFA ? </p> <p>But, my other part of brain is also thinking that NFA exists only in theory, so we cannot compare it's efficiency with DFA. </p> https://cs.stackexchange.com/questions/9389/-/9391#9391 4 Answer by saadtaame for Can we say DFA is more efficient than NFA? saadtaame https://cs.stackexchange.com/users/2499 2013-02-01T16:03:54Z 2013-02-01T16:35:09Z <p>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.</p> <p>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.</p> https://cs.stackexchange.com/questions/9389/-/9393#9393 15 Answer by Khaur for Can we say DFA is more efficient than NFA? Khaur https://cs.stackexchange.com/users/5366 2013-02-01T16:26:09Z 2013-05-16T16:00:21Z <p>There are two answers, depending on how you define efficient.</p> <h2>Compactness of representation</h2> <p><em>Telling more with less</em>: NFAs are more efficient. </p> <p>Converting a DFA to an NFA is straightforward and does not increase the size of the representation. </p> <p>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.</p> <h2>Computation</h2> <p><em>Running it fast</em>: DFAs are more efficient.</p> <p>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).</p> https://cs.stackexchange.com/questions/9389/-/9394#9394 1 Answer by vonbrand for Can we say DFA is more efficient than NFA? vonbrand https://cs.stackexchange.com/users/6447 2013-02-01T16:34:47Z 2013-02-01T16:34:47Z <p>If you use the <em>purely theoretical</em> "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.</p> https://cs.stackexchange.com/questions/9389/-/12082#12082 1 Answer by Raphael for Can we say DFA is more efficient than NFA? Raphael https://cs.stackexchange.com/users/98 2013-05-17T06:50:14Z 2013-05-17T06:50:14Z <p>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.</p> <p>Looking <em>only</em> 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".</p> <p>With respect to this measure, both automata models are <em>equivalent</em>, 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.</p> https://cs.stackexchange.com/questions/9389/-/12083#12083 2 Answer by Untitled for Can we say DFA is more efficient than NFA? Untitled https://cs.stackexchange.com/users/7410 2013-05-17T07:17:56Z 2013-05-17T07:17:56Z <p>Just adding to answers above:</p> <p>NFAs <em>can</em> be computationally more efficient than DFAs, in the sense that they can be simulated on a parallel processor.</p> <p>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.</p> https://cs.stackexchange.com/questions/9389/-/12084#12084 1 Answer by A.Schulz for Can we say DFA is more efficient than NFA? A.Schulz https://cs.stackexchange.com/users/2205 2013-05-17T07:39:06Z 2013-05-17T07:39:06Z <p>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.</p> <p>Other than this I agree with Raphael that it depends very much what you mean with <em>efficiency</em> and on the implementation.</p> https://cs.stackexchange.com/questions/9389/-/59976#59976 -3 Answer by deepali kaushik for Can we say DFA is more efficient than NFA? deepali kaushik https://cs.stackexchange.com/users/54025 2016-06-24T10:35:38Z 2016-06-24T10:35:38Z <p>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</p>