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

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