Follow Us :

Gate2018 cs Q15

0. Let N be an NFA with n states. Let k be the number of states of a minimal DFA which is equivalent to N. Which one of the following is necessarily true?

  • Option : D
  • Explanation :
    n is a number of state of given nfa (may not be minimal) k is a number of states of equivalent min dfa. First, we have to convert nfa to dfa using a subset construction algorithm and we get an equivalent dfa which will have atmost 2n states. Then we can convert this dfa to a minimal dfa and get a minimal dfa with k states where k ≤ 2n.
Cancel reply

Your email address will not be published. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *