# Proving that $(A \cup B)^* = A^*(BA^*)^*$

I would like to prove that $(A \cup B)^* = A^*(BA^*)^*$, where * means the Kleene star.

I would like to use induction to prove this equality but I do not how to proceed and how is the best way to set the induction hypothesis.

• Input size is not that helpful. Better use induction on the number of occurrences of $B$. Commented Mar 22, 2018 at 9:47
As already stated in the comments, it is easy to see that $$A^*(BA^*)^* \subseteq (A\cup B)^*$$ as every word $$x$$ in $$A^*(BA^*)^*$$ can be written as a concatenation of words that are either in $$A$$ or in $$B$$.
We show that the other containment holds. Consider a word $$x \in(A\cup B)^*$$. Then $$x$$ can be written as $$w_1\cdot w_2 \cdots w_k$$, where $$k\geq 0$$ and for all $$i\in [k]$$, it holds that $$w_i\in A$$ or $$w_i \in B$$ -- note that $$x = \epsilon$$ can be obtained as a concatenation of length $$k=0$$. If $$x = \epsilon$$, or for all $$i\in [k]$$, $$w_i\in A$$, then clearly $$x$$ is in $$A^*(BA^*)^*$$. Otherwise, let $$1\leq i_1 < i_2 < \cdots be the maximal sequence of indices (maximal w.r.t the number of induces) such that for all $$t\in [n]$$, we have that $$w_{i_t}\in B\setminus A$$. Thus, for all $$i\notin \{i_t\}_{t\in [n]}$$, we have that $$w_i\in A$$. We can now write $$x$$ as $$x = w_1\cdot w_2 \cdots w_{i_1} \cdot w_{i_1 + 1} \cdots w_{i_2} \cdot w_{i_2+1} \cdots w_{i_n} \cdot w_{i_n+1} \cdots w_k$$
Now it is not hard to see that $$x \in A^*(BA^*)^*$$. Indeed, the prefix $$w_1 \cdot w_2\cdots w_{i_1 - 1}$$ of $$x$$ is in $$A^*$$, and the suffix $$w_{i_1} \cdot w_{i_1 + 1} \cdots w_{i_2} \cdot w_{i_2+1} \cdots w_{i_n} \cdot w_{i_n+1} \cdots w_k$$ of $$x$$ is in $$(BA^*)^*$$: every $$w_{i_t}$$ is in $$B$$, and every $$w_{i}$$, for $$i\notin \{i_t\}_{t\in[n]}$$, is in $$A$$. Hence, $$w_{i_t} \cdot w_{i_t+1} \cdots w_{i_{t + 1} - 1} \in BA^{i_{t+1}-i_{t} - 1}$$ (for $$t = n$$, we let $$i_{n+1}$$ refer to $$k+1$$).