3
$\begingroup$

(all automata sizes are expressed in number of states in this question)

There exist NFAs of size $n$ for which the smallest DFA recognizing the same language is of size at least $2^n$.

Let $\Sigma$ be a vocabulary, and let's consider $n$ regular languages $L_i \subseteq \Sigma^*$ respectively recognized by $n$ DFAs $D_i=\{Q_i, q^0_i, F_i , \delta_i \}$ whose size are bounded by $m$.

We consider the epsilon-free NFA $N$ built by merging the $n$ DFAs such as $N=\{Q=\bigcup Q_i, q^0, F=\bigcup F_i , \delta \}$ where $\delta = \bigcup \delta_i$ with the additional constraint that $\forall \sigma \in \Sigma \, \delta(q^0, \sigma) = \{q | \delta_i(q_i^0, \sigma)=q \, \, 0 \leq i \leq n \}$ (note that in $N$ the $q^0_i$ are not anymore initial states since there is a unique initial state $q^0$).

Let $D_N$ be the DFA resulting from the powerset construction of $N$ and $D_N^M$ be the DFA resulting from the minimisation of $D_N$.

Is the size of $D_N^M$ at most $2^{1+\sqrt{mn}}$ ?

An equivalent question is : let $L \subseteq \Sigma^*$ be the language resulting from the union of the $n$ regular languages $L_i$, is the size of the smallest DFA recognizing $L$ always below $2^{1+\sqrt{mn}}$ ?

I would appreciate if possible, some papers related to this problem or a proof/counter-example.

Many thanks, Luz

$\endgroup$
4
$\begingroup$

No. Asymptotically, the size can be as large as $\sim m^n$.

Let $p_1,\dots,p_n$ denote the $n$ largest prime numbers that are at most $m$. Let

$$L_i = \{x : x \not\equiv 0 \pmod{p_i}\},$$

where we assume the number $x$ is expressed in unary. Then $L = L_1 \cup \dots \cup L_n$ has the form

$$L = \{x : x \not\equiv 0 \pmod q\},$$

where $q = p_1 \times \dots \times p_n$.

Note that, with this construction, each $L_i$ has a DFA of size at most $m$ (in particular, of size $p_i$). However, the minimal DFA for $L$ has size $q$, which is close to $m^n$. In particular, the size of the minimal DFA for $L$ is asymptotically larger than $2^{1 + \sqrt{mn}}$ (as a function of $n$, treating $m$ as fixed).

$\endgroup$
  • 1
    $\begingroup$ @Evil, you're right: it wouldn't. I guess I wasn't thinking clearly. OK, so my answer presents a lower bound, and there's a nearly-matching upper bound ($m^n$ is an upper bound). Thanks! $\endgroup$ – D.W. Feb 18 '17 at 0:51
  • $\begingroup$ Thank you very much for your answer :-) I'm working on it to understand it well. $\endgroup$ – Luz Feb 18 '17 at 8:32
  • $\begingroup$ Am I right: each DFA is a cycle of $p_i$ $a$-transitions. Each cycle size $<$ $m$ is minimal because size is a prime. The DFA for $L$ is minimal because it's the product of all the cycles and the sizes of two cycles starting from each state can not be congruent (correct ?) which makes all states indistinguable. Even if the size $q$ is $<$ $m^n$ (because all $n$ primes have decreasing size below $m$), q remains close to $m^n$ (why ?) and as $n \rightarrow \infty$ when $m$ is fixed we get $m^n \geq 2^{1+\sqrt{mn}}$ since $2^{1+\sqrt{mn}} = 2.(2^{\sqrt{m/n}})^n$ ($n$ is at denominator under $m$). $\endgroup$ – Luz Feb 18 '17 at 8:33
  • $\begingroup$ @Luz, correct. If $m$ is large, the prime number theorem ensures that there are lots of prime numbers that are smaller than $m$ but not much smaller than $m$ (in particular, they'll probably fall in approximately the range $[m - n \log m, m)$). $\endgroup$ – D.W. Feb 18 '17 at 8:35
  • $\begingroup$ This method with prime numbers is very nice :-) It is useful to find upper bounds by creating large minimal disjoint DFAs. I have still a last question (sorry)... $\endgroup$ – Luz Feb 18 '17 at 9:42
3
$\begingroup$

Let $\Sigma$ be an alphabet of size $n$. For each $\sigma \in \Sigma$, let $L_\sigma$ be the language of all words not containing $\sigma$. Each $L_\sigma$ is accepted by a DFA with $m=2$ states. It is well known that $L = \bigcup_{\sigma \in \Sigma} L_\sigma$ requires $2^n = m^n$ states to be accepted by a DFA.

$\endgroup$
  • $\begingroup$ Thank you for your answer which show that the size of the alphabet matters. But if we bound the alphabet to two symbols $\Sigma=\{a, b\}$ ? Does it still hold ? We would have to exclude from each $n$ languages $L_\sigma$ not only one symbol $\sigma$ but rather one word $w$ which would lead the $n$ DFAs for each language $L_w$ to be of size $m=|w|+1$. But some words $w$ would share a common prefix, and $w$ will not be exclusive to each $L_w$ as $\sigma$ was for each $L_\sigma$. Thus, the union language $L$ would not necessarily require $(|w|+1)^n = m^n$ states, in this case. $\endgroup$ – Luz Feb 18 '17 at 15:46
  • $\begingroup$ Given an alphabet $\Sigma=\{a, b\}$, I wonder if using the method with cycles of size prime (as told in the post of @D.W.) could lead to an interesting upper bound. As the DFAs are bounded by $m$, the number of primes of size $m$ would not be anymore bounded by $m$ but rather by $2^m$. Thus we could create $n \leq 2^m$ such DFAs which could lead to an upper bound of $m^n < {m}^{2^m}$. Again we get an upper bound ${m}^{2^m}$ that get rid of $n$. Even if the powerset construction guarantees a upper bound of $2^{mn}$, for large $n$ the number of states will stay at most ${m}^{2^m}$. Correct ? $\endgroup$ – Luz Feb 18 '17 at 16:02

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.