1
$\begingroup$

Let $\Sigma$ be an alphabet of size $2$, and let's consider $n$ regular languages $L_i \subseteq \Sigma^*$ respectively recognized by $n$ minimal DFAs $D_i$ whose size are bounded by $m$. As the number $k$ of minimal DFAs of size at most $m$ is finite, there exists a function $f$ that returns this number $k=f(m)$.

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 $D_L$ recognizing $L$ always below $m^{f(m)}$ ?

And if so, how can we find a precise definition/close-form of $f(m)$ ?

My intuition is as follows : the size of a DFA resulting from the union of two DFAs $A$ and $B$ is not greater than $|A|.|B|$. Thus, if there are not more than $f(m)$ minimal DFAs of size at most $m$ then the size of the minimal DFA for the union of the $D_i$ can not exceed $m^{f(m)}$. Sounds correct ?

Considering that for $|\Sigma|=2$ the transition function of a DFA of size at most $m$ is a graph. Since the nodes degree is bounded by $2$, for each node there are $m^2$ possibilities of pairs of arcs. In this graph there are at most $m$ possible choices of initial state and at most $2^m$ possible choices of final states sets. Thus, the maximum number of DFAs of size at most $m$ is $f(m) \leq m^{2m}.m.2^m = 2^m.m^{2m+1}$.

Thus we can conclude that for $|\Sigma|=2$ the maximal number of states required for the union of $n$ DFAs of size at most $m$ is bounded by $m^{f(m)} = m^{2^m.m^{2m+1}}$.

We can then generalize to an arbitrary alphabet $\Sigma$ : the bound becomes $f(m) \le 2^m.m^{|\Sigma|m+1}$. But it looks like this bound could be tighter though...

Does someone have a better estimate ?

One motivation to find a tighter bound is that if we fix the amount $S$ (in number of states) of memory that is available on a computer then we could easily get the maximal size $m$ that the $n$ DFAs must not exceed in order to guarantee the complete computation of the minimal DFA $D_L$ for the union of the $n$ DFAs.

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

Many thanks, Luz

$\endgroup$
  • $\begingroup$ The total possiblities of $\delta$ looks like $|Q|^{|Q|*|\Sigma|}$ so why have you consider $2^{2m}$ in the calculation of $f(m)$? $\endgroup$ – Deep Joshi Feb 20 '17 at 6:09
  • $\begingroup$ You are right ! Sorry... I have corrected my post. Thank you. $\endgroup$ – Luz Feb 22 '17 at 9:32
  • $\begingroup$ $|Q|^{|Q|\times|\Sigma|}$ is an overestimation really. When we talk about minimal DFA we can remove many possibilities of $\delta$. $\endgroup$ – Deep Joshi Feb 23 '17 at 8:30
  • $\begingroup$ Yes it's an overestimation. A tighter upper bound is available in this post $\endgroup$ – Luz Feb 23 '17 at 9:40
1
$\begingroup$

Yes. There is a simple proof.

You say that $L_i$ are recognized by DFAs of size $\le m$, and that there are at most $f(m)$ possible such DFAs. Therefore, there are at most $f(m)$ possible such languages. If $n \ge f(m)$, then $L_1,\dots,L_n$ must contain some repetitions (some language appears multiple times). Remove all repeated instances, so the $L_i$ are unique. Then at that point we have $n \le f(m)$. In other words, without loss of generality we can assume $n \le f(m)$.

Now the union of $n$ such languages can be recognized by a DFA of size at most $m^n$ (by a product construction), and $n \le f(m)$, so the union of $n$ such languages can be recognized by a DFA of size at most $m^{f(m)}$.

$\endgroup$
  • $\begingroup$ Thank you. What about the upper bound I give ? Do you think that it is possible to find a tighter upper bound ? $\endgroup$ – Luz Feb 21 '17 at 8:35
  • $\begingroup$ This leads me to the question of : how to prove that no tighter upper bound exists ? Is there some smart math method to do so ? $\endgroup$ – Luz Feb 21 '17 at 9:11
0
$\begingroup$

A better upper bound for $f(m)$ is given in this post with $f(m) \leq \frac{2^m.m^{|\Sigma|m}}{(m-1)!}$.

$\endgroup$

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.