an NFA whose corresponding DFA has at least $2^n - \alpha$ reachable states [duplicate]

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.

• Does this answer your question? NFA with exponential number of states when determinized Note that most examples go from $n+1$ states to $2^n$ states, which does not satisfy your bounds. I believe the solution by J.-E. Pin does what you want. Commented Jun 9, 2022 at 23:26