Let $a,b,c$ be regular expressions. Prove by transformation that $$(a^*b^*+c)^* \equiv (a+ (b+c)^*)^*$$
I tried to start with the second term
$$(a + ((b+c)^*))^* = (a^*(b+c)^*)^* = (a^*(b^*c^*)^*)^*$$
but am stuck here. Can you please help me to go on?
Thanks!
[Edit:]
Transformation rules:
- $a + b = b + a$
- $(a + b) + c = a + ( b + c)$
- $\epsilon a = a = a \epsilon$
- $(a b) c = a (b c)$
- $a(b + c) = ab + bc$
- $(a + b)c = ac + bc$
- $\epsilon^* = \epsilon$
- $(a^*)^* = a^*$
- $(\epsilon + a)^* = a^*$
- $(a^*b^*)^* = (a+b)^*$
- $(ab)^*a = a(ab)^*$
Here is the solution: $$(a + ((b+c)^*))^* = (a^*(b+c)^*)^*=(a+(b+c))^*$$ $$=((a+b)+c)^*=((a+b)^*c^*)^*=((a^*b^*)^*c^*)^*=(a^*b^*+c)^*$$
I used these rules: