# Prove the following: $L^2 \subseteq L$ if and only if $L = L^+$

I have the following problem in an assignment in my introduction to automata and formal languages course:

Prove that $L^2 \subseteq L$ if and only if $L = L^+$

But this problem highlights some ambiguity I have regarding languages:

I know that given any alphabet $\sum$, I can create the empty string $\lambda$. But, does every language contain $\lambda$? As far as I understand it, it's perfectly acceptable to define a language without $\lambda$, in which case the "if and only iff" clause seems to break:

Say I define a Language with alphabet {$a,b$}. so:

$L = L^+ = \{ a , b , aa , ab , ba , bb , aaa , aab ...\}$

$L^2 = \{aa, ab, ba, bb, aaa, ...\}$

In which case, obviously, if $L^2 \subseteq L$

But, this also works with:

$L = L^* = \{\lambda, a , b , aa , ab , ba , bb , aaa , aab ...\}$

$L^2 = \{a,b, aa, ab, ba, bb, aaa, ...\}$

Here, again, $L^2 \subseteq L$

so, why the if and only if?

• What are you asking? iff is used for biconditionals, that means you have implications in both directions. In your example, neither of the statements hold. $L^2$ contains $aa$, which is not in $L$, and $L^+$ also contains lots of stuff not in $L$. There would only be a problem if you had a language for which one property holds but not the other one. To prove a biconditional, you assume that the property on one side holds, and prove the other one, and then do the same thing in the other direction. – martin.koeberl May 11 '17 at 14:24
• sorry, I'll clarify my example. The idea was that I create a base $L$, and then just use the $L^+$ and $L^*$ when testing the statement they give me. – Devilius May 11 '17 at 14:26
• What's the end of the second to last sentence of your question? The implication seems incomplete. (And I also don't see how it could be relevant, the statement you're trying to prove doesn't mention $L^*$) Also, $L\subseteq L^+$ is true for any language, so $L=L^+$ and $L^+\subseteq L$ are equivalent. (Clearly, you will use that $L^+\subseteq L$, since the other inclusion is vacuously true.) – martin.koeberl May 11 '17 at 14:34
• It will be better if you use a language with more than one variable. Your definition of $L^2$ is wrong. If $L=\{a,ab,abb,abbb,\dots\}$ then $L^2=\{aa,aab,aabbb,\dots,aba,abab,ababb,\dots\}$. It consists of concatenations of two elements of $L$, not necessarily the same element of $L$. So in your case, $L^2=\{aa,aaa,aaaa,aaaaa,\dots\}$. The elements don't have to be even length, in particular. – Thomas Andrews May 11 '17 at 14:35
• If $\lambda\in L$ then since $L\subseteq L^+$, we'll have $\lambda\in L^+$. – Rick Decker May 11 '17 at 15:07

Your second example is not a counterexample to the "only if". In that case, $L$, $L^+$, $L^*$ and $\{a,b\}^*$ are all equal.
Claim. Let $L$ be a language. Then $L^2 \subseteq L$ if and only if $L = L^+$.
Proof. ($\Leftarrow$) Suppose that $L = L^+$. Then $L^2 \subseteq L$, since $L^2 \subseteq L^+$.
($\Rightarrow$) Suppose that $L^2 \subseteq L$. We prove by induction that $L^n \subseteq L$ for all $n \geq 1$. For $n = 1$, this is trivial; for $n = 2$, this is the assumption. So, let $n \geq 2$ and assume that $L^n \subseteq L$. Then \begin{align*} L^{n+1} & = L L^n \\ & \subseteq L^2 \text{ (using the induction hypothesis)} \\ & \subseteq L \text{ (by assumption).} \end{align*} So, for all $n \geq 1$, $L^n \subseteq L$ and therefore $L^+ = \bigcup_{n\geq 1}L^n \subseteq L$. Since also $L \subseteq L^+$, it follows that $L = L^+$.
It should be clear that the implication in one direction, $L=L^+\Rightarrow L^2\subseteq L$, holds when we replace "$+$" with "$*$". However, the converse implication doesn't.
Consider the language $L=\{a^{2k}\mid k>0\}$. Here we have $L^2\subseteq L$ but it's obvious that $L\ne L^*$, since $\lambda\notin L$ but $\lambda\in L^*$