How would I go about proving the following two regular expressions are equal to one another:

( a + b )* a ( a + b )* b( a + b )* = (a + b)* ab(a + b)*

I can "see" why they are equal to one another because the second ( a + b )* is a redundant term as the expression will always have an ab together. But how can I formalize this and show, in general, that this is true ?

  • 1
    $\begingroup$ Note: This question has been cross-posted to Math.SE, where it has received 2 answers. That can be found here. $\endgroup$ Feb 9, 2016 at 0:03

1 Answer 1


Convert both regular expressions to a DFA, compute the symmetric difference of the two DFA's using a product construction, and then check whether the result accept the non-empty language. Each of those steps is described here on this site. See also Does this regular expression equal this automata? for a very similar question.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.