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
Upper bound for the union of $n$ DFAs of size at most $m$?
automata;finite automata;pushdown automata
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)}$.