2
$\begingroup$

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?
$\endgroup$
9
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – BCS
    Nov 2 '10 at 20:28
  • $\begingroup$ 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$. $\endgroup$ Nov 3 '10 at 14:12
  • $\begingroup$ 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. $\endgroup$
    – BCS
    Nov 3 '10 at 20:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.