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 about other related case:


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.