Question

Given an arbitrary non-deterministic finite automation (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least

• A. $N^2$
• B. N!
• C. 2N
• D. $2^N$

Answer 1

The correct option is D $2^N$

For an arbitrary NFA with N states, the maximum number of states in an equivalent minimized DFA is $2^N$