That's a pretty good application, though I have to say that I would probably opt for a statistical approach to verification.
Generate a bunch of random strings, pass them through the stricter test, and then pass it's output through the quicker. If the second results set equals the first, you're good to go.
With a good knowledge of what the regex are attempting to match, it should be relatively easy to generate random datasets that exercise most of the edgecases, or at least a statistically computable subset thereof.
And that was my point. Using the knowledge of what the regex are trying to match, and statistics, is probably much easier than try to crosscompare to regex, for which the comparison is only valid if you can first prove that at least one of the regex is itself "correct"which is an extremely hard task to start with.
Unless you can:
 use a definite dataset to prove one of them.
In which case you could use the same dataset to prove the other.
 You accept a statistical proof of one.
Which again, could be used to prove the other.
Proving the compatibility of two unprovable entities doesn't really buy you a lot unless the comparability test is very quick and cheapwhich doesn't appear to be the case here.
There is no point in measuring something, unless you are pretty sure that your ruler is accurate!
Examine what is said, not who speaks.
Silence betokens consent.
Love the truth but pardon error.
