GATE Computer Science (CS) 2018 Shift 1 Solved Paper

Question : 28 of 65

Marks: +1, -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?

$k ≥ 2^{n}$
$k ≥ n$
$k ≤ n^{2}$
$k ≤ 2^{n}$

Validate

Solution:

n is number of state of given nfa (may not be minimal)

k

is number of states of equivalent min dfa. First we have to convert nfa to dfa using subset construction algorithm and we get an equivalent dfa which will have atmost

2^{n}

states. Then we can convert this dfa to a minimal dfa and get a minimal dfa with k states where

k ≤ 2^{n}

Go to Question:

Prev Question

Next Question