How should one proceed to prove (or find) if two regular expressions are same or equivalent?

finitenessofinfinity picture finitenessofinfinity · Jan 22, 2012 · Viewed 13.9k times · Source

For example, in an assignment given to me, we were asked to find out if two regular expressions are equal or not.

(a+b+c)*  and ((ab)**c*)*

My question is how is one supposed to do that? If I draw the transition graphs for both and then run a few strings through it and show that both of the TGs are able to accept it, is that a sufficient proof ? If not, how do I do it? Is there a mathematical/axiomatic approach towards this?

Thanks in advance.

EDIT: There is another thing that I'd like to clear which is kind of related to this question. Are the two FAs depicted in the photo below the same?

enter image description here

i.e. Are (1) and (2) in the above picture the same?

Answer

nachito picture nachito · Jan 22, 2012

Two regular expressions R and T are equivalent if the language defined by R (i.e., the set of strings generated by regular expression R) is equal to the language defined by T. To prove equivalences for regular expressions, we use containment proofs from set theory. That is, if S1 is the set of strings generated by regular expression R, and S2 is the set of strings generated by regular expression T, we must prove that S1 ⊆ S2 and S2 ⊆ S1. Both directions are necessary to prove equality of sets.

-- From the lecture notes of CSc 4340 GSU Fall 09 (Dr. Raj Sunderraman)