I am new to automata theory and have a problem in understanding equivalence of regular expressions, though I can go for the construction procedure of minimized DFAs to prove that both are equal.
I need to prove the following property using different Kleene star properties:
$$(a+b)^* = b^*(ab^*)^*$$
A report by Aceto contains an axiomatization of the equational theory of regular expressions, called "classical" by Conway (Table 1 on page 5). One of the axioms is very similar to what you're after: $(a+b)^* = (a^*b)^*a^*$. Using these axioms, we can derive your identity as follows (using associativity (C3, C10) for free): $$ \begin{align*} (a+b)^* &= (b+a)^* && C2 \\ &= (b^*a)^*b^* && C11 \\ &= (\epsilon+b^*(ab^*)^*a)b^* && C12 \\ &= b^* + b^*(ab^*)^*ab^* && C9 \\ &= b^*(\epsilon + (ab^*)^*ab^*) && C8 \\ &= b^*(\epsilon + \epsilon(ab^*\epsilon)^*ab^*) && C6,C7 \\ &= b^*(\epsilon ab^*)^* && C12 \\ &= b^* (ab^*)^* && C7 \end{align*} $$
Applying kleen star on both side
((a+b)*) *= ( b * (ab*)*) *
But ((a+b)* )* = (a+b)* as we know (a*)* = a*
( b * (ab*)*) * = (b + (ab*))* as we know (a+b)* =(a* b*)*
I can use b* as empty string as its redundant.
Even if we are using b* as empty string the expression gives all strings of a's and b's. So using b* wont add new strings to the set.
So we can say
(b + (ab*))*= (b+a) * = (a+b)*
Proved
