Why does a translated DFA usually not have $2^n$ states?

Question

If we translate an NFA to a DFA, it can have $2^n$ states at the maximum. However, this usually does not happen? Why is that so and what is the condition such that the translated DFA will have $2^n$ states?

Answer 1

The upper bound $2^n$ is indeed achieved by the automaton ${\mathcal A}_n = (Q_n, A, E_n, \{0\}, \{0\})$, with $A = \{a, b\}$, $Q_n = \{0, 1, \ldots, n-1\}$ and \begin{multline*} E_n = \{(i, a, i+1) \mid 0 \leq i \leq n-1\} \cup \{(n-1, a, 0)\} \cup {}\\ \{(i, b, i) \mid 1 \leq i \leq n-1\} \cup \{(i, b, 0) \mid 1 \leq i \leq n-1\}\} \end{multline*}

Now, the problem with your question is that usually is not a mathematical term. It is actually a difficult question to find a rigorous model of random NFA. Such a model is proposed in [1], but the average complexity of the conversion NFA to DFA according to such a model is still an open problem, as far as I can know.

[1] P.C. Héam and J.-L. Joly, On the uniform random generation of non deterministic automata up to isomorphism, Implementation and application of automata, 140-152, LNCS 9223, Springer, Cham, (2015).