<p>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:</p>

<blockquote>
  <p>Sheng Yu.  State Complexity of Regular Languages.  Journal of Automata, Languages and Combinatorics, 2001.</p>
</blockquote>

<p>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.</p>

<p>The bound is simple and can surely be extended to three DFAs.</p>

CC BY-SA 2.5
2010-11-02T20:28:47.780Z
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
CC BY-SA 2.5
2010-11-03T14:12:52.230Z
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
CC BY-SA 2.5
2010-11-03T20:25:11.837Z
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
CC BY-SA 2.5
2010-11-02T19:58:33.513Z
2010-11-02T19:58:33.513Z
John Watrous
<p>Given RegEx <code>A</code> and <code>B</code> where the size of the compiled DFAs are <code>m</code> and <code>n</code> respectively, what is the upper bound on the size of the compile DFA for <code>A|B</code>? It shouldn't be hard to show that it can't be more than <code>n*m</code> but can a lower upper bound be shown?</p>

<p>What about other related case:</p>

<ul>
<li>What is the expected case for real world examples? Is it less than <code>n+m</code>?</li>
<li>What about the three part case with <code>A</code>, <code>B</code> and <code>C</code>?</li>
</ul>

<fl.formal-languages><regular-expressions><dfa>
upper bound on the size of a DFA for A|B given the DFAs for A and B?
BCS
# upper bound on the size of a DFA for A|B given the DFAs for A and B?

(Asked by: username_0 on 2010-11-02)

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`?

**Tags:** fl.formal-languages, regular-expressions, dfa


---

## 1 answers

### Answer by username_1 on 2010-11-02. Score: 9

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.

> **Comments:**
> **username_0**: 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.  
> **username_1**: 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$.  
> **username_0**: 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.  

---

