A question about operations on languages.

Question

I come across this problem on a book. It states that: for languages A and B, $(A\cup B)^* = (A^*B^*)^*$. I know that the definition of star closure is $\left(\bigcup^{\infty}_{i=1}\right)A^i$. But so far, I have no idea how to tackle the problem.

I tried this: assume that $x\in (A\cup B)^*$, then $x\in (A\cup B) ^0\cup (A\cup B)^1\cup ..... $ It implies that $x\in (A\cup B)^i $ for some integer i, $i\in [0,\infty)$. Then I get stuck.. I'd appreciate if you can help!

Answer 1

Hints:

• $A \cup B \subseteq A^*B^*$
• $A^*B^* \subseteq (A\cup B)^*(A\cup B)^*$
• $(X^*)^* = X^*$

I hope this helps $\ddot\smile$

Answer 2

Hint: a word in $(A\cup B)^*$ looks something like this: $$w=a_1a_2b_1a_3b_2b_3a_4a_5a_6\ ,$$ where all the $a_i$ come from $A$ and all the $b_j$ come from $B$.

Words in $(A^*B^*)^*$ consist of a concatenation of words form $A$, followed by a concatenation of words from $B$, then $A$ again and so on. Can you see how to put $w$ into this form?

Also don't forget that as you are asked to prove equality, you have to do the reverse of this too.