# Inductive approach on Kleene star proof

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?

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^*$$.

• So I have two questions: One is how do I proceed about using the $(L^*)^* = L^*$ property? My second is I see how my induction fails but logically, I can't see why my assumption did not work. I know the Kleene star demands that my $k=\infty$. Is this why it failed? – Ayumu Kasugano Oct 10 '18 at 5:46
• "I can't see why my assumption did not work". Here is another counterexample. For example, $L_1=\{a\}$ and $L_2=\{b\}$. Then $L_1^*L_2^*=a^*b^*$ contains word $a^2$ as well as $ab$. So $(L_1^*L_2^*)^{(1)}$, as a superset of $L_1^*L_2^*$, also contains $a^2$ as well as $ab$. However, $(L_1\cup L_2)^{(1)}$=$(L_1\cup L_2)^0 + (L_1\cup L_2)^1$=$\{\epsilon\} + \{a, b\}$=$\{\epsilon, a, b\}$, which does not contain $a^2$ nor $ab$. – John L. Jul 29 '19 at 17:49