7
$\begingroup$

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,

  • 0
    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?2011-06-23
  • 0
    @Nate Eldredge: Yes, I agree. For a particular example, I just use common sense and it works out pretty well. Thanks.2011-06-23

3 Answers 3

7

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.

  • 0
    For strangers, DFA means deterministic finite automaton ?2011-06-22
  • 0
    @Emre Yes, that's correct.2011-06-22
  • 1
    Heh. Yeah, solution to this one is "highly non trivial" as some like to say.2011-06-22
  • 1
    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.2011-06-23
6

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

  • 0
    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.2011-06-22
  • 0
    @Charles, yes, I realised that after I'd turned off the computer for the night.2011-06-23
  • 0
    Good for you. +1 for a solution that works, even though it's difficult.2011-06-23
6

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.