1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Ayumu Kasugano Oct 10 '18 at 5:46
  • $\begingroup$ You can check the answers to prove that A** = A*. $\endgroup$ – Apass.Jack Oct 10 '18 at 7:14
  • $\begingroup$ "I can't see why my assumption did not work". Actually, I would put it in a different way. Can you tell why your assumption should work? For me, I cannot think why your assumption should work, except by the extended influence of the equality in the problem. By the way, you have never written out your assumption explicitly. $\endgroup$ – Apass.Jack Oct 10 '18 at 7:19
  • $\begingroup$ It looks like you are not aware that you can accept an answer if you are the questioner. It is part of a basic protocol and etiquette to try accepting the best answer that has answered your question by clicking on the check mark beside the answer to toggle it from greyed out to filled in. You can check the FAQ entry on when someone answers. You can also check how important is accepting an answer and why should we accept answers. $\endgroup$ – Apass.Jack Oct 10 '18 at 10:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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