NFA–Minimized DFA State Bounds: Necessarily True Statements

Verified Sources

Sep 12, 2026

Let $N$ be an NFA with $n$ states and let $M$ be the minimized DFA with $m$ states recognizing the same language $L(N)=L(M)$ . To compare $n$ and $m$ , the key tool is the subset construction: every DFA state corresponds to a set (subset) of NFA states reachable after reading some input. In the worst case, the subset construction can generate up to $2^n$ distinct subsets, so the corresponding (not necessarily minimized) DFA has at most $2^n$ states. After minimization, the number of states can only decrease, implying $m \le 2^n$ . This makes statement (i) necessarily true.

We can also see that statements (ii)–(iv) are not necessarily true by counterexamples: there are languages recognized by NFAs with few states whose minimal DFA has more states than $n$ , and also languages recognized by NFAs with few states whose minimal DFA has far fewer than $2^n$ states.

subset construction state minimization minimized DFA equivalent states reachable subset

Decide which statements are necessarily true

1
Step 1
An NFA with $n$ states yields at most $2^n$ distinct subsets of states in the subset construction DFA; minimization cannot increase states, so $m \le 2^n$ .
2
Step 2
Since the minimized DFA $M$ is a minimized version of an equivalent DFA from subset construction, $m \le 2^n$ must hold.
3
Step 3
The subset construction may create many DFA states, and the minimal DFA can be larger than the NFA state count; thus $n \le m$ is not guaranteed.
4
Step 4
Minimal DFAs can have multiple accepting states; there is no general theorem forcing exactly one accepting state.
5
Step 5
The $2^n$ bound is a worst case for subset construction, not necessarily achieved by the minimized DFA; many languages yield far fewer reachable subsets and many equivalent-state merges.

type="tip" title="Pro Tip" content="When comparing NFA and minimized DFA sizes, first bound the subset-construction DFA by $2^n$ , then remember minimization can only reduce the state count. That pattern typically settles “upper bound” statements like (i)."

type="warning" title="Common Pitfall" content="The bound $2^n$ refers to the subset-construction DFA before minimization, and even then only reachable subsets matter. Many problems fail because they assume all $2^n$ subsets are realized or that minimization preserves the worst case."

Evaluating the four options

(i) $m \le 2^n$

This is necessarily true. The subset construction creates a DFA whose states are subsets of the NFA’s $n$ -state set, so there are at most $2^n$ possible subsets. The minimized DFA $M$ recognizes the same language, and minimization cannot increase the number of states. Therefore $m \le 2^n$ .

subset construction minimized DFA reachable subset

(ii) $n \le m$

This is not necessarily true. There exist NFAs with $n$ states whose minimal DFA needs more than $n$ states (so $n \le m$ can hold), but the reverse can also happen: NFAs with very few states can recognize languages whose minimal DFA has $m < n$ as well. Since the question asks what is necessarily true for all such pairs, one counterexample either way would disprove it. The general relationship is not an inequality in that direction.

(iii) $M$ has one accept state

This is not necessarily true. A DFA can have multiple accepting states, and the minimal DFA for many regular languages necessarily has multiple accepting states depending on the Myhill–Nerode equivalence classes that correspond to accepting continuations.

Myhill–Nerode theorem accepting state equivalence class

(iv) $m = 2^n$

This is not necessarily true. $2^n$ is a worst-case upper bound for the subset construction DFA, and even then the minimized DFA may have far fewer states because many subsets are unreachable and many DFA states are equivalent under minimization.

worst-case upper bound unreachable state equivalent states

From NFA size to minimized DFA size

Subset construction

Step A

Convert NFA transitions to DFA transitions over subsets of NFA states; at most $2^n$ subsets."

Reachability filtering

Step B

Only subsets reachable from the start subset become actual DFA states."

State minimization

Step C

Merge equivalent DFA states; minimized DFA has $m$ states, with $m$ no larger than the pre-minimization DFA."

Knowledge Check

Question 1 of 4

Q1Single choice

Which statement about $m$ and $n$ is necessarily true for an NFA with $n$ states and the minimized DFA with $m$ states recognizing the same language?

m \le 2^n

n \le m

M has one accept state

m = 2^n

Explore Related Topics

Ambiguous Grammars in Formal Language Theory: Choosing the Correct Option

Maximum number of edges in a bipartite graph: why $\lfloor n^2/4\rfloor$ is optimal

Designing a Turing Machine to Compute the Sum of Two Positive Integers

Browse all research articles