Algorithm: Intersection of two regexps

Question

I'd like to figure out (in runtime) whether or not two regular expressions intersect (i.e. if they do there exist one or more string the matches both regular expressions).

Algorithm needs to be pretty fast as I need to loop through a database and check existing values.

Found some theory on this but no implementations?

Answer 1

The obvious solution would be to convert the regexes to DFAs, compute the intersection of the DFAs (trivial) and see if there's anything the resulting DFA can accept (also trivial). The only hard part is converting the regexes to DFAs, which requires some work.

Answer 2

Here's an implementation in Haskell using partial derivatives of regexps. A comment to that post points out an issue with the approach in Chris Dodd's answer.

Answer 3

What about checking first one and then the other with the input that passed the first?