Question

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 necessairly true ?

• A. $k\ge n$
• B. $k\le 2^n$
• C. $k\le n^2$
• D. $k\ge 2^n$

Answer 1

The correct option is B $k\le 2^n$

n is number of states of given NFA (may not be minimal)k is number of states of equivalent min DFA. First we 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 $k\le 2^n$