Proving the regular expression identity $(a(a + b)^*)^* = (ab^*)^*$

Question

I'm struggling to prove the regular expression identity $$(a(a+b)^*)^* = (ab^*)^*$$

The recommendation is to use induction on the star operator. My strategy was to first prove that $$(a(a+b)^*)^* \subseteq (ab^*)^*$$ and then prove $$(ab^*)^* \subseteq (a(a+b)^*)^*$$

I started with the first one, using induction on the inner start of the left side. So the base case is: $$(a\epsilon)^* \subseteq (ab^*)^*$$ Which holds. Then For the inductive hypothesis I assume: $$(aX)^*\subseteq(a)$$ And then set out to prove $$(aX(a+b)^*)^* \subseteq (ab^*)^*$$ Now I know there is a set identity that would make it sufficient to prove: $$(aX(a+b)^*) \subseteq (ab^*)$$ Then by the I.H: $$(a(ab^*)^*(a+b)^*) \subseteq (ab^*)$$ And this is as far as I've been able to get! I don't know how to manipulate what I have here to reach the goal. Am I on the right track? Any hints, identities that could be useful to help me finish this proof. Thanks.

Answer 1

$a(a + b)^*$ is a followed by any number of a's and b's.
$((a(a + b)^*)^*$ is the same with the addition of the empty string.

$(ab^*)^*$ includes the empty string and any string of a's and b's begining with a.

So the regular expressions are equivalent.
The advise of induction with * is confusing.
Do they mean double induction for the iterated use of *?

This Mathjax thing can be obnoxious when the preview is different than how the answer appeares, thus requiring additional, unexpected editing.

Answer 2

Let me follow your strategy. The inclusion $(ab^*)^* \subseteq (a(a+b)^*)^*$ is easy to prove as follows $$ b \subseteq a+b \implies b^* \subseteq (a+b)^* \implies ab^* \subseteq a(a+b)^* \implies (ab^*)^* \subseteq (a(a+b)^*)^* $$ For the opposite inclusion, I interpret the recommendation as follows: prove by induction on $n$ that, for all $n$, $$ (1) \quad a(a+b)^n \subseteq (ab^*)^*. $$ For $n = 0$, the result is trivial. Suppose that the formula holds for $n$. Then $$ a(a+b)^{n+1} = a(a+b)^n(a+b) \subseteq (ab^*)^*(a+b) = (ab^*)^*a +(ab^*)^*b $$ It suffices now to observe that $(ab^*)^*a \subseteq (ab^*)^*ab^* \subseteq (ab^*)^*$ and $(ab^*)^*b \subseteq (ab^*)^*$ to prove (1).

Of course, (1) implies $a(a+b)^* \subseteq (ab^*)^*$, whence $(a(a+b)^*)^* \subseteq (ab^*)^*$.

N.B. For a purely formal proof, you could try to use the axioms of a Kleene algebra, but it is probably not in the spirit of what you were asked for.