Intersection of two regular expressions

Question

Im looking for function (PHP will be the best), which returns true whether exists string matches both regexpA and regexpB.

Example 1:

$regexpA = '[0-9]+';
$regexpB = '[0-9]{2,3}';

hasRegularsIntersection($regexpA,$regexpB) returns TRUE because '12' matches both regexps

Example 2:

$regexpA = '[0-9]+';
$regexpB = '[a-z]+';

hasRegularsIntersection($regexpA,$regexpB) returns FALSE because numbers never matches literals.

Thanks for any suggestions how to solve this.

Henry

Answer 1

For regular expressions that are actually regular (i.e. don't use irregular features like back references) you can do the following:

1. Transform the regexen into finite automata (the algorithm for that can be found here(chapter 9) for example).
2. Build the intersection of the automata (You have a state for each state in the cartesian product of the states of the two automata. You then transition between the states according to the original automata's transition rules. E.g. if you're in state x1y2, you get the input a, the first automaton has a transition x1->x4 for input x and the second automaton has y2->y3, you transition into the state x4y3).
3. Check whether there's a path from the start state to the end state in the new automaton. If there is, the two regexen intersect, otherwise they don't.