# upper bound on the size of a DFA for A|B given the DFAs for A and B?

Given RegEx A and B where the size of the compiled DFAs are m and n respectively, what is the upper bound on the size of the compile DFA for A|B? It shouldn't be hard to show that it can't be more than n*m but can a lower upper bound be shown?

• What is the expected case for real world examples? Is it less than n+m?
• What about the three part case with A, B and C?

The upper bound of $nm$ follows from the usual Cartesian product construction that you will find in just about any book on automata theory. A lower bound of $nm$ is observed (for the case $\operatorname{gcd}(n,m) = 1$) in this paper:

Sheng Yu. State Complexity of Regular Languages. Journal of Automata, Languages and Combinatorics, 2001.

The lower bound is proved for DFAs that I would consider to exist in the real world -- but if you want an expectation you will have to be more precise about the distribution from which $A$ and $B$ are drawn.

The bound is simple and can surely be extended to three DFAs.

• For "real would" examples, I guess the constraint is RE that you find someone using rather than create. As with anything that steps outside theory it's ill defined and hard to play with.
– BCS
Nov 2 '10 at 20:28
• The DFAs that Yu uses to prove the lower bound of $nm$ are natural, as opposed to being contrived for the sake of the proof: they simply decide whether the length of the input string is divisible by $n$ or $m$, respectively. Although I have no formal justification for saying so, my intuition is that the number of states required to recognize $A\cup B$ is likely to be on the order of $nm$ (as opposed to $n+m$, say) unless there is some special relationship between $A$ and $B$. Nov 3 '10 at 14:12
• My intuition is that most pairs of RE will quickly diverge to states where only A or only B is a possible match and will very often be non-diverging before that.
– BCS
Nov 3 '10 at 20:25