619 views

What is the relation between $DFA$ and $NFA$ on the basis of computational power ?

1. $DFA$ > $NFA$
2. $NFA$ > $DFA$
3. Equal
4. Can't be said

NFA = DFA in terms of computational power.
Equal relationship

Option C Equal

Both $DFA$  and $NFA$  having a same computational power

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.

Option C) is correct , Computational power of both are equal.
by

1
1,195 views