# Prove $(aa^*bb^*)^*=ϵ+a(a+b)^*b$ using regex laws

I tried to prove this by starting at RHS:

$$ϵ+a(a+b)^*b = ϵ+a(a^*b^*)^*b$$
But I dont know how to convert $$(a^*b^*)^*$$ to something else that will be helpful.
Any ideas?

• The question in the title is different from the question in the body. Im assuming you made a writing mistake in the title Jun 27 at 14:54
• Or did you mean that this is what you tried to show, as a process of proving the question in the title? Jun 27 at 14:55
• @nirshahar Yes this was the process. Jun 27 at 14:56

First, we want to show that $$L((aa^*bb^*)^*)\subseteq L(\epsilon + a(a+b)^*b)$$: Take any word $$w\in L((aa^*bb^*)^*)$$. Its not hard to show that either $$w=\epsilon$$, or $$w$$ must start with $$a$$ and end with a $$b$$ (rewrite $$bb^*$$ as $$b^*b$$, it will help to prove this). Then, it will be clear that $$w\in L(\epsilon+a(a+b)^*b)$$.
Now we want to show that $$L(\epsilon + a(a+b)^*b)\subseteq L((aa^*bb^*)^*)$$: Take any word $$w\in L(\epsilon + a(a+b)^*b)$$. If $$w=\epsilon$$ its obvious why $$w\in L((aa^*bb^*)^*)$$. Otherwise, prove by induction over $$|w|$$ the length of $$w$$, that you can split $$w$$ in the following way: $$w=x_1x_2,\dots,x_k$$ for some $$k\in\mathbb{N}$$ such that $$x_i \in L(aa^*b^*b)$$.
Hint: define $$x_1$$ to be the substring of $$w$$ starting at the first element, and stopping at the first index $$l$$ such that $$w_l=b$$ but $$w_{l+1}=a$$. If there is no such index $$l$$, then take $$x_1:=w$$.