patternMinor
Proving that $(A \cup B)^* = A^*(BA^*)^*$
Viewed 0 times
provingthatcup
Problem
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 !
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 !
Solution
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$).
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$).
Context
StackExchange Computer Science Q#89636, answer score: 2
Revisions (0)
No revisions yet.