Inductive approach on Kleene star proof

Question

I'm having trouble proving the following: If $L_1$ and $L_2$ are languages then: $$(L_1^*L_2^*)^* = (L_1\cup L_2)^*$$ I could be on the wrong track here, but I figured an inductive approach is a good way?

My approach was this: If I use my notation $L^{(n)} = \lambda+L+L^2+...+L^n$ so that I have a kind of 'partial' Kleene star I start the induction:

1.) Base case $n=0$:

$(L_1^*L_2^*)^{(0)} = \lambda = (L_1\cup L_2)^{(0)}$ and so this works

2.) Assume true for some $n=k\geq0$ such that $(L_1^*L_2^*)^{(k)} = (L_1\cup L_2)^{(k)}$

3.) Now I want to see how $(L_1^*L_2^*)^{(k+1)}$ evaluates to:

$(L_1^*L_2^*)^{(k+1)} = (L_1\cup L_2)^{(k)}+(L_1^*L_2^*)^{k+1}$ where I used the inductive hypothesis. I know I should try to see if this RHS can give me the union with a (k+1) but I don't know how to manipulate this anymore. Am I on the wrong track or am I just not seeing the algebra properly?

Answer 1

It looks like you are on the wrong track.

While it is trivially true that $(L_1^*L_2^*)^{(0)} = \lambda = (L_1\cup L_2)^{(0)}$ where $\lambda$ is the language consisting of the empty word, it is more often than not that $(L_1^*L_2^*)^{(1)}\neq (L_1\cup L_2)^{(1)}$. For example, if either $L_1$ or $L_2$ has a non-empty words, the left side $(L_1^*L_2^*)^{(1)}=(L_1^*L_2^*)^{(1)}\supseteq (L_1^*\cup L_2^*)$ has infinitely many word. However, if furthermore we let both $L_1$ and $L_2$ be finite languages, the right side $(L_1\cup L_2)^{(1)}$ is a finite language as well. A concrete counterexample can be given by $L_1=\{a\}$ and $L_2=\lambda$.

Here is an approach to move forward. Can you prove that for any language $L$, $(L^*)^*=L^*$? The use of that equality is that you can deduce that $(L_1\cup L_2)^{*}=\left((L_1\cup L_2)^{*}\right)^*$.

Here is another approach that I like. Intuitively, it is easy to "see" the equality $(L_1^*L_2^*)^* = (L_1\cup L_2)^*$. Note that A word in $L_1^*L_2^*$ is some number of words in $L_1$ followed by some number of words in $L_2$.

• A word in $(L_1^*L_2^*)^*$ is some number of words in $L_1$ followed by some number of words in $L_2$, possibly followed by some number of words in $L_1$ followed by some number of words in $L_2$, ..., possibly followed by some number of words in $L_1$ followed by some number of words in $L_2$. Here "some number of" means zero or more.
• A non-empty word in $(L_1\cup L_2)^*$ is a word in $L_1$ or $L_2$, possibly followed by a word in $L_1$ or $L_2$, ..., possibly followed by a word in $L_1$ or $L_2$.

Can you see how a word in the former language must be a word in the latter language? Can you see how a word in the latter language must be a word in the former language? If you can, try expressing those "how" in rigorous terms. That would be a proof.

---

Here is a related exercise.

Let $L_1$ and $L_2$ be languages such that $L_1\subset L_2^*$ and $L_2\subset L_1^*$. Prove that $L_1^*=L_2^*$.