Prove that $(A\cup B)^\star=A^\star (BA^\star)^\star$

Question

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

I'm trying to to prove this equality using induction. However, I'm kinda stuck about how is the best way to set the induction hypothesis and how would be the best way to apply.

First, I want to prove that $ (A \cup B)^\star \subseteq A^\star(BA^\star)^\star$

Let $x \in (A\cup B)^\star$

Base:

$|x| = 0$. Then, $x=\lambda \in (A^\star B^\star)^\star$

I'm thinking to set the induction hypothesis to:

If $y \in (A \cup B) ^\star$ and $|y| < |x|$, then $y \in (A^\star B^\star)^\star$. Is this correct?

Then, applying the pass:

Suppose that $|x| > 0$. As $x \in (A \cup B)^\star$ and $|x| > 0$, then exists $w_1...w_k$ factors $\in A \cup B$ so that $x = w_1...w_k$.

Basically, I dont know how I would be able to apply the Hypothesis Induction here.

Am I right so far? How should I proceed?

Could someone please help? Thanks !

Answer 1

I'm not so sure about how easy an inductive proof is here but here's a way to do it equationally. I'll assume the standard Kleene algebra axiomitization which includes $B\cup AX\subseteq X\Rightarrow A^*B\subseteq X$. I'm treating $\lambda$ as the 1 here (so e.g. if we're talking about regular sets then $\lambda=\{\varepsilon\}$).

Using $AA^*\subseteq A^*$ and the fact that $\lambda\subseteq A^*$ so $B^*=\lambda B^*\subseteq A^*B^*$ along with $\lambda\subseteq A^*(BA^*)^*$, write \begin{align*} (BA^*)^*&\subseteq (BA^*)^*\\ \lambda(BA^*)^*&\subseteq A(BA^*)^*\\ (BA^*)^*&\subseteq A^*(BA^*)^*\\ BA^*(BA^*)^*&\subseteq A^*(BA^*)^*\\ A^*(BA^*)^*\cup BA^*(BA^*)^*&\subseteq A^*(BA^*)^*\cup A^*(BA^*)^*\\ AA^*(BA^*)^*\cup BA^*(BA^*)^*&\subseteq A^*(BA^*)^*\\ \lambda\cup AA^*(BA^*)^*\cup BA^*(BA^*)^*&\subseteq A^*(BA^*)^*\\ \lambda\cup (A\cup B)A^*(BA^*)^*&\subseteq A^*(BA^*)^*\\ (A\cup B)^*\lambda&\subseteq A^*(BA^*)^*\\ (A\cup B)^*&\subseteq A^*(BA^*)^*. \end{align*}

For the other direction, start out with $A\subseteq (A\cup B)$ and $B\subseteq (A\cup B)$ so $A^*,B^*\subseteq (A\cup B)^*$. Now write \begin{align*} A^*(BA^*)^*&\subseteq A^*(BA^*)^*\\ &\subseteq (A\cup B)^*(BA^*)^*\\ &\subseteq (A\cup B)^*((A\cup B)A^*)^*\\ &\subseteq (A\cup B)^*((A\cup B)(A\cup B)^*)^*\\ &\subseteq (A\cup B)^*((A\cup B)^*)^*\\ &\subseteq (A\cup B)^*(A\cup B)^*\\ &\subseteq (A\cup B)^*. \end{align*} Notice I'm using $A^*A^*\subseteq A^*$ and $A^*{^*}\subseteq A^*$ without proof but these can be derived from the axioms.

Answer 2

Let me revise Kleene Stars.   $A^\star$ is the concattenation of zero-or-more strings of $A$ units.   So we have the recursion: $$A^\star = \{\epsilon\}\cup AA^\star$$

$(A\cup B)^\star$ is a string of none or more units which are each either $A$ or $B$.

$A^\star(BA^\star)^\star$ is a string of none or more units of $A$ followed by none or more strings which are each a single $B$ followed by none or more units of $A$.

---

$$\begin{split}A^\star(BA^\star)^\star &= (\{\epsilon\}\cup AA^\star)(BA^\star)^\star \\ &= (BA^\star)^\star\cup AA^\star(BA^\star)^\star \\ &= \{\epsilon\}\cup BA^\star(BA^\star)^\star\cup AA^\star(BA^\star)^\star\\&= \{\epsilon\}\cup (A\cup B)A^\star(BA^\star)^\star \\ &~~\vdots &\leftarrow\text{what goes here?} \\ &= \{\epsilon\}\cup (A\cup B)(A\cup B)^\star \\ &= (A\cup B)^\star \end{split}$$