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?

  • $\begingroup$ 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. $\endgroup$ – martin.koeberl May 11 '17 at 14:24
  • $\begingroup$ 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. $\endgroup$ – Devilius May 11 '17 at 14:26
  • $\begingroup$ 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.) $\endgroup$ – martin.koeberl May 11 '17 at 14:34
  • $\begingroup$ 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. $\endgroup$ – Thomas Andrews May 11 '17 at 14:35
  • 1
    $\begingroup$ If $\lambda\in L$ then since $L\subseteq L^+$, we'll have $\lambda\in L^+$. $\endgroup$ – 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^*$


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.