Regular Expression Collision Detection

Question

We say that two regular expressions e1and e2 face , if there is any string s, so that both e1and e2match s.

Is there a simple (effective) way to check if two regular expressions collide without repeating over the set of all possible lines in our dictionary?

Note 1: I do not know if this is caused in a different way in the literature. Maybe I just don't have the right name to search for this.

Note 2: The ideal answer for me is written in PHP code, but I accept any suggestion, not PHP.

Answer 1

So, after further research, it looks like this is called the intersection of regular expressions in the literature.

It is possible and, apparently, it is not difficult to implement, but there seems to be no official PHP support.

The key to implementing a simple algorithm depends on translating regular expressions into a state machine. Read the attached links for a better understanding of the solution.

Stackoverflow related questions:

The intersection of two regular expressions

Calculate if two infinite sets of regex solutions intersect

Unofficial library for PHP:

https://github.com/KendallHopkins/FormalTheory

Edit: Adding a code snippet to check for intersections using the Kendall Hopkins library:

function doRegexIntersection($regex_string_1, $regex_string_2) {
    $lexer = new FormalTheory_RegularExpression_Lexer();
    $nfa1 = $lexer->lex( $regex_string_1 )->getNFA();
    $nfa2 = $lexer->lex( $regex_string_2 )->getNFA();
    return FormalTheory_FiniteAutomata::intersection( $nfa1, $nfa2 )->validSolutionExists();
}