# Polynomial-time Compute the Number of States resulting from the NFA to DFA (greedy) conversion?

The canonical NFA to DFA conversion, starting with an NFA with $$n$$ states, can result in a DFA with $$2^n$$ states. However, in many cases, there are states that are "unnecessary," such as when minimizing the resulting DFA. The most common case is when states are "unreachable" from the corresponding start state.

I am interested in the following question: if we have an NFA with $$n$$ states and $$q$$ symbols, is there a $$\mathrm{poly}(n, q)$$-time algorithm to output the number of states that the standard conversion (and minimizing, if possible) to a DFA would produce? Note that producing the DFA itself can take exponential time.

It is well known that NFA universality (given an NFA, does it accept all words?) is PSPACE-complete. This easily implies that the following problem is PSPACE-complete:

Given an NFA, is there an equivalent DFA with exactly one state?

To show that the problem is in PSPACE, note that in order to show that an NFA isn't equivalent to a DFA with exactly one space, it suffices to show that its language is not universal (known to be in PSPACE) and non-empty (can be checked in P).

To show that the problem is PSPACE-hard, we reduce from NFA universality. Given an NFA $$A$$ over the alphabet $$\Sigma = \{0,1\}$$, we construct an NFA for the language $$L = \epsilon + 0\Sigma^* + 1L(A)$$; this requires adding a constant number of states. The language $$L$$ is never empty, and it is universal iff $$L(A)$$ is, hence $$L(A)$$ is universal iff $$L$$ is accepted by a DFA having a single state.

• can we determine in polynomial time if the language accepted by an NFA is finite? The case of DFA is simple, but translating the NFA to DFA is exponential... Thanks Allot! May 9, 2022 at 14:12
• This looks like an unrelated question, which is better asked separately. May 9, 2022 at 14:12