# 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:
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 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$. – John Watrous Nov 3 '10 at 14:12