0
$\begingroup$

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 ?

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

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

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

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