Alex Rivera | Logout

Mutually exclusive regular expressions

Asked 2010-06-03T16:40:41.923
13

If I have a list of regular expressions, is there an easy way to determine that no two of them will both return a match for the same string?

That is, the list is valid if and only if for all strings a maximum of one item in the list will match the entire string.

It seems like this will be very hard (maybe impossible?) to prove definitively, but I can't seem to find any work on the subject.

The reason I ask is that I am working on a tokenizer that accepts regexes, and I would like to ensure only one token at a time can match the head of the input.

regex mutual-exclusion
Edit
Report

1 Answer

7

If you're working with pure regular expressions (no backreferences or other features that cause them to recognize context-free or more complicated languages), what you ask is possible. What you can do is convert each regex to a DFA, then (since regular languages are closed under intersection) combine them into a DFA that recognizes the intersection of the two languages. If that DFA has a path from the start state to an accepting state, that string is accepted by both input regexen.

The problem with this is that the first step of the usual regex->DFA algorithm is to convert the regex to a NFA, then convert the NFA to a DFA. But that last step can result in an exponential blowup in the number of DFA states, so this will only be feasible for very simple regular expressions.

If you are working with extended regex syntax, all bets are off: context-free languages are not closed under intersection, so this method won't work.

answered 2010-06-03T17:10:14.620

Your Answer