in Theory of Computation recategorized by
591 views
1 vote
1 vote

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
in Theory of Computation recategorized by
591 views

2 Comments

NFA = DFA in terms of computational power.
0
0
Equal relationship
0
0

2 Answers

0 votes
0 votes

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.

 

0 votes
0 votes
Option C) is correct , Computational power of both are equal.
Answer:

Related questions