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.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
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.