Approximate Regular Expression Equivalence

Question

Theoretically regex equivalence is a hard problem having naive solution with exponential space and time complexity. But for practical purposes, is there an approximate equivalence measure for regexes?

I'm thinking about generating random strings from first regex and then checking it against the other and then repeat it the other way. Is there a more elegant check available?

Relevant links:

PS : I want to code the approach in java though general solutions and ideas are welcome.

@jnovacho can you elaborate on linked automaton equivalence solution. — damned, Jan 03 '14 at 11:22
comparing DFAs is not clear in the solution. Am I supposed to check the equivalence at isomorphic level - which takes exponential time. — damned, Jan 03 '14 at 11:26

score 1 · Answer 1 · edited Apr 13 '17 at 12:57

I think your solution will not work perfectly.

Suppose you want to compare regexes like ".*1" and ".*2" , With your naive algorithm , it will keep on executing without a halt.

Better you use NFA , and minimize it for both regexes.

If you are reaching a similar DFA , then you can compare both regexes.

Refer this for equivalence of DFAs.

One more way I can suggest :

Suppose let S1 and S2 be the regexes to compare. As of I know S1 will produce a language L1 (Set of strings producesd by S1) , And S2 will produce a language L2 .

We can check equivalence of two languages .

Refer Deciding equivalence of regular languages for more details .

You can check DFA equivalence. – Sujith PS Jan 03 '14 at 11:27 — Sujith PS, Jan 03 '14 at 11:27

Approximate Regular Expression Equivalence

1 Answers1