How would I prove that these two regexes are equal to one another? $$ (a \cup b)^* = (b^*(a\cup\lambda)b^*)^*$$

I'm permitted to use the following regular expression identities.


  • 4
    $\begingroup$ Please do not delete your questions after receiving answers. That's against our policies. $\endgroup$ – Raphael Sep 25 '17 at 7:54

One of the equalities 12 tell us that now $(u\cup v)^* = u^*(vu^*)^*$. Applying this to the last expression we obtain $(b\cup (a\cup\lambda))^*$.

Also $(u\cup \lambda)^* = (u^*\lambda^*)^* = (u^* \lambda)^* = (u^*)^* = u^*$.

Do you have associativity of $\cup$ so that $(b\cup (a\cup\lambda))^* = ((b\cup a)\cup\lambda))^*$? It should be a basic property.

  • $\begingroup$ No I don't have associativity. Which is why I can't seem to prove this directly from the table itself. $\endgroup$ – Skeletor Sep 24 '17 at 23:46
  • $\begingroup$ Also, re-reading your answer I don't see how your second line for $ u^* $ is used? But, I can derive what we would get from associativy by starting with $ (b \cup a)^* $ and using the second line in reverse. $\endgroup$ – Skeletor Sep 25 '17 at 0:02
  • $\begingroup$ That part in reverse is what I meant. I do not know how to solve the remainder without using associativity. sorry. $\endgroup$ – Hendrik Jan Sep 25 '17 at 11:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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