How do you check if two regex's describe the same pattern?

Question

Sometimes you may come up with two different regex's for one task. I wonder how you check if two regex's describe the same pattern?

• Are there some algorithms for that checking?

• Are there some (online) tools for that checking?

For example, I have two regex's here Can we rewrite lookbehind in terms of the if-then-else?, I would like to know if they are the same.

Thanks.

Answer 1

Equivalence of regular languages is decidable (see Hopcroft, Motwani, Ullman: Introduction to Automata Theory, Languages and Computation, Chp 4.4) which is also the foundation for minimising the DFA. Intuitively, if the minimised DFAs are equivalent (upto renaming of states), than the languages generated/accepted by the regular languages are the same. So, the answer to your first question is yes.

I'm sure there are online tools, but in the worst case, you can ask 'flex' or equivalent to minimise the automata and you can implement a simple tool, which checks if they can be consistently renamed.

This SO entry is also relevant:

Regular expressions Equivalence