GATE CS 2001 Q1.6 — Regular Expressions and Finite Automata

To find the maximum number of states in a minimized DFA equivalent to an $N$-state NFA, we look for the worst-case scenario where the subset construction yields a DFA that cannot be further minimized.

1. Subset Construction Upper Bound

Given an NFA with $N$ states, the power set of its states has $2^N$ possible subsets. Therefore, the equivalent DFA constructed via subset construction can have at most $2^N$ states.

2. Achievability of the $2^N$ Bound

There exist languages accepted by an $N$-state NFA for which the equivalent minimized DFA requires exactly $2^N$ states. For example, consider a language where we need to track the $N$-th symbol from the right-hand end of the input string. An NFA can easily guess this position and transition to the accept state using $N$ states, whereas any DFA must remember the last $N$ symbols read, requiring $2^N$ distinct states. Since all these $2^N$ states are pairwise distinguishable, the minimized DFA must also have $2^N$ states.

Thus, the maximum number of states in an equivalent minimized DFA is at least $2^N$.