1
$\begingroup$

(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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – rici Apr 15 at 16:28
  • $\begingroup$ @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. $\endgroup$ – Hilder Vítor Lima Pereira Apr 15 at 20:58
  • $\begingroup$ 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. $\endgroup$ – rici Apr 15 at 21:13
  • $\begingroup$ 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... $\endgroup$ – rici Apr 16 at 0:32
  • $\begingroup$ 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? $\endgroup$ – rici Apr 16 at 0:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.