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?

Tripura

Read en.wikipedia.org/wiki/… – Abbacy

Already read that... Got anything else? – Tripura

@Gumbo: That link is of course for the theoretical (mathematical) model; actual regex languages are far richer and include constructs (notably back references) means they are no longer /regular/. This of course only makes the problem harder :-( . – Factional

@Richard: The question is tagged with theory and is talking about languages. So I doubt it is a practically oriented question. – Abbacy

Not all actual regex implementations go beyond the finite-state/regular language framework. – Korwin

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.

Arcuation

Answer 2

Here's a conceptually simple answer (assuming L1 and L2 are regular).

1) Find DFAs D1 and D2 for L1 and L2 respectively.

2) Construct D'1 and D'2 from D1 and D2 by swapping accepting/non-accepting states (note that D'1 accepts exactly ~L1 and D'2 accepts ~L2 where ~ means "complement of")

3) Use the standard product construction three times to produce a DFA that accepts exactly (L1 intersect ~L2) union (L2 intersect ~L1)

4) Check to see if the DFA from part 3 accepts any strings by checking each accepting state for reachability from the start state.

5) If the DFA from part 3 accepts any strings, then L1 <> L2. Otherwise, L1=L2

There are a huge number of heuristics you could use to speed this up, but conceptually, this is probably the simplest algorithm. A good reference for the product construction in part 3 is "Automata and Computability" by Dexter Kozen.

Gauhati