Upper bound for the union of $n$ DFAs of size at most $m$?

Question

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

Answer 1

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)}$.

Answer 2

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