Trying to find an algorithm which takes 2 regular expressions and tells whether they are equivalent

Question

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).

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..

Also, I know that if L1 - L2 and L2 - L1 are empty, then L1 = L2.

Anyone good with theory here?

Answer 1

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

http://arxiv.org/PS_cache/arxiv/pdf/0907/0907.5058v1.pdf

Dig through references of the article to find other solutions that may be less efficient, but easier to implement.