Given an arbitrary Non-deterministic Finite Automata (NFA)

Home » Theory of Computation » Theory of computation miscellaneous » Question

Given an arbitrary Non-deterministic Finite Automata (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least

1. N²
2. 2^N/sup>
3. 2N
4. N!

Correct Option: B

In DFA any subset of the N states (for N element set N subsets possible) can become a new state and they can remain even when the DFA is minimized. So, maximum we can get N states for the minimized DFA.