# Characterization of NFA whose equivalent (minimal) DFA has exponential number of states

(I don't know if there are standard names for this, so) Let's say that a Nondeterministic Finite Automaton (NFA) is $$n$$-expansive if it has $$n$$ states and any Deterministic Finite Automaton (DFA) recognizing the same language has at least $$2^{n/2}$$ states.

Let $$E_n$$ be the set of all $$n$$-expansive NFAs.

Is there a characterization to $$E_n$$?

Given any NFA $$A$$, is there a way to test if $$A \in E_n$$ in polynomial time in $$n$$ (therefore, without constructing the minimal DFA of $$A$$)?

The lower bound $$2^{n/2}$$ is arbitrary. If you know a characterization for other similar exponential bounds (e.g. $$2^{n-1}$$ or $$2^{n/10}$$), it will be very helpful.

• That definition isn't workable because for any NFA $n$ is fixed, and so is $2^n$. Any constant $c$ is $\Theta(2^c)$ (or $\Theta(c')$ for any other constant $c'$). You could try to characterise a family of NFAs of different sizes, where the expansive predicate applies to the family as a sequence (without $n$ qualification) but that's not really the same. – rici Apr 15 at 16:28
• @rici I see what you mean. However, I don't have a family of NFA in mind. I just would like to know if given a NFA, there is some way to test if it will blow up when determinized and if there is a way to characterize the NFAs that blow up, do you understand? Maybe I can replace the asymptotic lower bound by a somehow arbitrary but still representative one... I will edit the question. Thank you for commenting. – Hilder Vítor Lima Pereira Apr 15 at 20:58
• i understand your desire, but it's really not well-defined. Say you have a 10-state NFA. What's the smallest number of states in the DFA which would qualify as exponential? 100? 200? 500? Even a 2-state DFA could be exponential if the NFA has some characteristic which guarantees at least $2^{n-9}$ DFA states. – rici Apr 15 at 21:13
• By the way, if this is a practical rather than theoretical problem, you might be interested in this one. Let $\mu$ be an ordered list of a subset of $\Sigma$. A sentence in $\Sigma^*$ is $\mu$-complete if it contains all the symbols in $\mu$. The language of $\mu$ complete sentences is regular, and can be described by the regular expression which is the union over all permutations of $\mu$ of $\Sigma\pi_1\Sigma...\pi_k\Sigma$ (where $\pi$ is a permutation). The NFA then has $O(k\; k!)$ states and the determinized DFA is subject to exponential blowup, with the standard algorithm... – rici Apr 16 at 0:32
• So that's totally impractical for even small values of $k=|\mu|$. (The original for this problem is "words containing all vowels", where $k$ is five. The regex above blows flex up.) However, the minimised DFA "only" has $2^k$ states, which is 32 in the case of $k=5$. The question is: how to handle such regular expressions without generating the $2^{k\;k!}$-state intermediate DFA? – rici Apr 16 at 0:37