I have a large collection of regular expression that when matched call a particular http handler. Some of the older regex's are unreachable (e.g. a.c* ⊃ abc*) and I'd like to prune them.
Is there a library that given two regex's will tell me if the second is subset of the first?
I wasn't sure this was decidable at first (it smelled like the halting problem by a different name). But it turns out it's decidable.
On
Trying to find the complexity of this problem lead me to this paper.
The formal definition of the problem can be found within: this is generally called the inclusion problem
The inclusion problem for R, is to test for two given expressions r, r′ ∈ R, whether r ⊆ r′.
That paper has some great information (summary: all but the simplest expressions are fairly complex), however searching for information on the inclusion problem leads one directly back to StackOverflow. That answer already had a link to a paper describing a passable polynomial time algorithm which should cover a lot of common cases.
On
If the regular expressions use "advanced features" of typical procedural matchers (like those in Perl, Java, Python, Ruby, etc.) that allow accepting languages that aren't regular, then you are out of luck. The problem is in general undecidable. E.g. the problem of whether one pushdown automaton recognizes the same context free (CF) language as another is undecidable. Extended regular expressions can describe CF languages.
On the other hand, if the regular expressions are "true" in the theoretical sense, consisting only of concatenation, alternation, and Kleene star over strings with a finite alphabet, plus the usual syntactic sugar on these (character classes, +, ?, etc), then there is a simple polynomial time algorithm.
I can't give you libraries, but this:
For each pair of regexes r and s for languages L(r) and L(s)
Find the corresponding Deterministic Finite Automata M(r) and M(s)
Compute the cross-product machine M(r x s) and assign accepting states
so that it computes L(r) - L(s)
Use a DFS or BFS of the the M(r x s) transition table to see if any
accepting state can be reached from the start state
If no, you can eliminate s because L(s) is a subset of L(r).
Reassign accepting states so that M(r x s) computes L(s) - L(r)
Repeat the steps above to see if it's possible to eliminate r
Converting a regex to a DFA generally uses Thompson's construction to get a non-deterministic automaton. This is converted to a DFA using the Subset Construction. The cross-product machine is another standard algorithm.
This was all worked out in the 1960's and is now part of any good undergrad computer science theory course. The gold standard for the topic is Hopcroft and Ullman, Automata Theory.
On
I found a python regex library that provides set operations.
http://github.com/ferno/greenery
The proof says Sub ⊆ Sup ⇔ Sub ∩ ¬Sup is {}. I can implement this with the python library:
import sys
from greenery.lego import parse
subregex = parse(sys.argv[1])
supregex = parse(sys.argv[2])
s = subregex&(supregex.everythingbut())
if s.empty():
print("%s is a subset of %s"%(subregex,supregex))
else:
print("%s is not a subset of %s, it also matches %s"%(subregex,supregex,s)
examples:
subset.py abcd.* ab.*
abcd.* is a subset of ab.*
subset.py a[bcd]f* a[cde]f*
a[bcd]f* is not a subset of a[cde]f*, it also matches abf*
The library may not be robust because as mentioned in the other answers you need to use the minimal DFA in order for this to work. I'm not sure ferno's library makes (or can make) that guarantee.
As an aside: playing with the library to calculate inverse or simplify regexes is lots of fun.
a(b|.).* simplifies to a.+. Which is pretty minimal.
The inverse of abf* is ([^a]|a([^b]|bf*[^f])).*|a?. Try to come up with that on your own!
There is an answer in the mathematics section: https://math.stackexchange.com/questions/283838/is-one-regular-language-subset-of-another.
Basic idea:
It would be benificial if you would just compute the new transition and the resulting states, omitting all non reachable states from the beginning.