# How to prove two regular expressions are identical in mathematical way?

I'm currently working on "regular expression" exercises in the textbook ("An Introduction to Formal Languages and Automata"), and the problem that I'm facing is, most of the time, my solution is different than the book's ones. However, I realize that they could both express the same language, but I couldn't find a way to prove it. I wonder if is there a mathematical way (like induction) to prove that the two regular expression are actually identical? Any suggestion?

Thank you,

-
As the answers point out, doing this in general is difficult. But of course, some specific example might be easy, especially if it is a textbook exercise where the language accepted is simple, and both regular expressions were found by humans who were not trying to be perverse. Do you have a particular example in mind? –  Nate Eldredge Jun 23 '11 at 4:25
@Nate Eldredge: Yes, I agree. For a particular example, I just use common sense and it works out pretty well. Thanks. –  Chan Jun 23 '11 at 14:20

That's an extremely difficult problem. You could convert the regular expression to a DFA and minimize it, but that's PSPACE-complete...

I think procedures for determining equivalence for regular expressions is known to take at least exponential space and time and at most double exponential time, but I could be wrong.

-
For strangers, DFA means deterministic finite automaton ? –  Emre Jun 22 '11 at 20:19
@Emre Yes, that's correct. –  Nicolas Villanueva Jun 22 '11 at 20:24
Heh. Yeah, solution to this one is "highly non trivial" as some like to say. –  ItsNotObvious Jun 22 '11 at 20:52
Thank you. I guess it is actually difficult because the way they prove automaton and language is very ambiguous. In words, I can't convince myself that the proof is correct. I think I'd better find another book. –  Chan Jun 23 '11 at 2:57

Over a language $\Sigma$, given one DFA with states $S = \{s_i\}$ (of which $A \subseteq S$ are accepting) and transition function $\delta : S \times \Sigma \rightarrow S$ and another DFA with states $T = \{t_j\}$ (of which $B \subseteq T$ are accepting) and transition function $\zeta : T \times \Sigma \rightarrow T$ you can "easily" construct a DFA with states $U = S \times T$ (Cartesian product) and transition function $\eta((s_i, t_j), \sigma) = (\delta(s_i, \sigma), \zeta(t_j, \sigma))$. Then the two DFAs are equivalent iff the only states reachable in this Cartesian-product DFA are a subset of $(A \times B) \cup ((S \setminus A) \times (T \setminus B))$ - i.e. it's impossible to reach a state which is accepting in one of the original DFAs but not in the other.

Once you've translated the regular expressions to DFAs the time complexity is going to be $O(ST\Sigma)$.

-
A regular expression of size s can have a DFA of order 2^s, so your algorithm is (at least, in the worst case) exponential in time and space. –  Charles Jun 22 '11 at 22:56
@Charles, yes, I realised that after I'd turned off the computer for the night. –  Peter Taylor Jun 23 '11 at 7:14
Good for you. +1 for a solution that works, even though it's difficult. –  Charles Jun 23 '11 at 13:09

Salomaa (1966) gave two complete proof systems for proving that two regular expressions are equivalent ("identical"). If you can't access the link above, there is a description in Kozen's lecture notes. Kozen himself gave another complete proof system.

As mentioned above, it is PSPACE-complete whether a regular expression generates all possible strings (this is a particular case of regular expression equivalence known as universality). This doesn't necessarily mean that the proofs are necessarily long, only that they are hard to find.

-
Thank you very much. –  Chan Jun 23 '11 at 14:17