<p>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?</p>

CC BY-SA 3.0
2014-01-02T22:18:02.093Z
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...
siravan
CC BY-SA 3.0
2014-01-04T04:16:39.443Z
@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.
D.W.
<approximation-algorithms><automata-theory><regular-expressions>
Sub optimal regex equivalence
damned
# Sub optimal regex equivalence

(Asked by: username_0 on 2014-01-02)

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?

**Tags:** approximation-algorithms, automata-theory, regular-expressions

> **Comments:**
> **username_1**: 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...  
> **username_2**: @username_1 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.  

---

## 0 answers

