1
$\begingroup$

Is there an NFA with n states so that the DFA resulting from the standard conversion of the NFA to a DFA has at least $2^n - \alpha$ reachable states for some integer $\alpha \ge 1$?

Let $N= (Q, \Sigma, \mu, q_0, F)$ be the NFA. Construct a DFA $M = (Q',\Sigma, \delta, q, F')$ as follows: $Q' = \mathcal{P}(Q), F' = \{X \in Q' : X\cap F\neq \emptyset\}, q = \epsilon(\{q_0\})$. The standard construction is to construct a state for each subset of states of the NFA. Let $Q$ be the set of states of the NFA. Define the transition function of the DFA so that when reading a symbol x on a state $S\subseteq Q, \delta(S,x) = \epsilon(\cup_{q\in S}\mu(q, x)),$ where $\epsilon$ denotes the epsilon closure.

Obviously the exact accept states of the DFA or NFA don't really matter for this problem; it's mostly just the symbols used (I think an alphabet of size two should work) and the transition function that matters. I tried coming up with such an NFA for small cases of n (e.g. n = 1,2). I'm unsure how to construct such an NFA when n = 3. But I'm not sure how to come up with a general method. I think $\alpha = 1$ should work.

$\endgroup$
1

0