Detecting if two regexes could possibly match the same string

Question

Given two regular expressions, is it possible to detect whether there is any possible string that matches them both?

For example, given regexes A and ., I can see that string "A" matches them both. That's a simple case.

My question is for the broader case -- given any two valid regexes, would it be possible to definitively say whether there is any possible string that would match both regexes? Assume that there is no sample set of input strings to test. All I have are the regexes. I don't necessarily need to produce matching strings -- I just need to determine that there are possible strings that match both.

Will accept discussions for any of the common regex specifications -- .NET, Java, PERL, sed, grep, etc.

When you say "would it be possible" do you mean that a programmer could figure it out, or do you mean a constructive proof from an algorithm? — Bob Dalgleish, Mar 25 '14 at 22:12
Either way. I'm not even sure it's theoretically possible given the breadth of regex. — Michael Gunter, Mar 25 '14 at 22:17
use the position and the length of each RegEx match to determine overlaps. — alpha bravo, Mar 26 '14 at 02:51
@alpha: Please re-read the post. I've modified it so it's a little clearer. — Michael Gunter, Mar 26 '14 at 14:40
I'm afraid, for _common case_ no way: regex could match infinite set of strings - so it's non-deterministic problem (as intersection may be incomputable with finite count of algorithm steps) — Alma Do, Mar 26 '14 at 14:41

score 5 · Accepted Answer · answered Mar 26 '14 at 15:06

Basically, you want to test if the intersection of two RegExps is non-empty. Since intersection - just like complement - is a potentially expensive operation (it requires determinization of the NFA), it is not implemented in many RegExp implementations. One exception I know of is the BRICS Automaton Library, which allows enabling the intersection operator &.

To test the property in question, you could use the BRICS (Java) library like this:

RegExp re = new RegExp("(.) & (a)", RegExp.INTERSECTION); // Parse RegExp
Automaton a = re.toAutomaton(); // convert RegExp to automaton

if(a.isEmpty()) { // Test if intersection is empty
  System.out.println("Intersection is empty!");
}
else {
  // Print the shortest accepted string
  System.out.println("Intersection is non-empty, example: " + a.getShortestExample(true));
}

score 0 · Answer 2 · answered Mar 26 '14 at 14:57

Yes, it's possible theoretically.

But it basically comes down to try all possible options and see which matches both regexes. But it's more a theoretical computer science question, with modern day regular expressions in programming languages this would be a problem in NP (http://en.wikipedia.org/wiki/NP_(complexity))

If you're talking more about the formal language theory definition of a regular language, than I would say it should be possible by converting both regexes to a DFA and walk through both simultaneously to see what would match.

Detecting if two regexes could possibly match the same string

2 Answers2

Linked