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$ "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$. $\endgroup$ – Apass.Jack Jul 29 at 17:49

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.