Regex: Determine if two regular expressions could match for the same input?

Question

I want to find out if there could ever be conflicts between two known regular expressions, in order to allow the user to construct a list of mutually exclusive regular expressions.

For example, we know that the regular expressions below are quite different but they both match xy50:

'^xy1\d' '[^\d]\d2$' 

Is it possible to determine, using a computer algorithm, if two regular expressions can have such a conflict? How?

Answer 1

There's no halting problem involved here. All you need is to compute if the intersection of ^xy1\d and [^\d]\d2$ in non-empty.

I can't give you an algorithm here, but here are two discussions of a method to generate the intersection without resorting the construction of a DFA:

• http://sulzmann.blogspot.com/2008/11/playing-with-regular-expressions.html

And then there's RAGEL

• http://www.complang.org/ragel/

which can compute the intersection of regular expressions too.

UPDATE: I just tried out Ragel with OP's regexp. Ragel can generate a "dot" file for graphviz from the resulting state machine, which is terrific. The intersection of the OP's regexp looks like this in Ragel syntax:

('xy1' digit any*) & (any* ^digit digit '2')  

and has the following state machine:

While the empty intersection:

('xy1' digit any*) & ('q' any* ^digit digit '2') 

looks like this:

So if all else fails, then you can still have Ragel compute the intersection and check if it outputs the empty state machine, by comparing the generated "dot" file.