4
$\begingroup$

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.

Could someone please help? Thanks !

$\endgroup$
3
  • $\begingroup$ Maybe induction on the input size? Note the right hand side obviously belongs to the left hand side, you only need to prove the left hand side belongs to the right hand side. $\endgroup$
    – xskxzr
    Commented Mar 22, 2018 at 3:47
  • $\begingroup$ In addition, I think you can prove it directly without induction. $\endgroup$
    – xskxzr
    Commented Mar 22, 2018 at 3:54
  • $\begingroup$ Input size is not that helpful. Better use induction on the number of occurrences of $B$. $\endgroup$ Commented Mar 22, 2018 at 9:47

1 Answer 1

2
$\begingroup$

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 <i_n \leq k$ 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$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.