Regex Equivalence is a hard problem which in general takes exponential space and exponential time. Are there any approximation/sub-optimal algorithms with some theoretical guarantees over equivalence available?

  • $\begingroup$ I think a randomized algorithm should work. It is not difficult to generate a random string than satisfies a given regex in polynomial time. Then, you can test the string with the other regex. If it fails, the two are not equivalent. If it passes, you need more random strings... $\endgroup$ – siravan Jan 2 '14 at 22:18
  • 2
    $\begingroup$ @siravan is right. But, beware that such an algorithm might perform poorly on some regexps. Consider, e.g., $(ab)^{20}$ vs $(ab)^{20} \mid abaaaabababaababbbbb$. Here your probability of discovering that they differ is about $1/2^{20}$ per test case, assuming you are sampling from the uniform distribution over the strings that satisfy the regexp. Of course, that 20 could just as easily have been 100, in which case random testing (by sampling uniformly at random) ain't never gonna discover that these two regexps accept different languages. $\endgroup$ – D.W. Jan 4 '14 at 4:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.