<p>You can find a description of a reasonably efficient algorithm for testing r.e. equality here:</p>

<p><a href="http://arxiv.org/PS_cache/arxiv/pdf/0907/0907.5058v1.pdf" rel="nofollow">http://arxiv.org/PS_cache/arxiv/pdf/0907/0907.5058v1.pdf</a></p>

<p>Dig through references of the article to find other solutions that may be less efficient, but easier to implement.</p>
Trying to find an algorithm which takes 2 regular expressions and tells whether they are equivalent
<p>I'm trying to find out what the algorithm would be by being given two languages L1 and L2 to determine if they are equivalent (L1 = L2).</p>

<p>It's surprisingly difficult to come up with one as I've found, although I am pretty sure it needs to be converted to a DFA first and then reduce each of them to a minimal DFA..</p>

<p>Also, I know that if L1 - L2 and L2 - L1 are empty, then L1 = L2. </p>

<p>Anyone good with theory here?</p>