recategorized by
992 views
1 votes
1 votes

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
recategorized by

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

2 votes
2 votes
4 answers
1
admin asked Mar 31, 2020
1,631 views
The automaton which allows transformation to a new state without consuming any input symbols : $NFA$$DFA$$NFA - 1$All of the options
2 votes
2 votes
3 answers
2
admin asked Mar 31, 2020
1,576 views
Complement of a $DFA$ can be obtained by :making starting state as final state.make final as a starting state.making final states non-final and non-final as final.None of...
1 votes
1 votes
4 answers
3
admin asked Mar 31, 2020
3,616 views
Concatenation Operation refers to which of the following set operations : UnionDotKleeneNone of the options
1 votes
1 votes
2 answers
4