Characterization about Kleene Closure, when is a language $L=L^*$?

Question

I'm trying to find a characterization of when $L=L^*$.

I think I have one, but maybe is trivial, but I don't know if the proof is correct.

Claim: $L=L^* \Leftrightarrow L=LL$.

Proof:

If $L=L^*$ then is easy to see $LL \subseteq L$ so $L=LL$.

The other implication is in which I have doubts, I used a simple chain of equalities $$L=LL=\cdots=L^n=\cdots= \bigcup_{i\geq 0}L^i=L^*.$$

I would like to know if there is something wrong and specially if there's another characterization which is less trivial.

Answer 1

What your argument actually shows is $$ L = L^* \Rightarrow L=L^2 \Rightarrow L = L^+. $$ Indeed, suppose that $L = L^*$. On the one hand, $L^2 \subseteq L^* = L$. On the other hand, since $\epsilon \in L$, we have $L = \epsilon L \subseteq L^2$.

Next, suppose that $L = L^2$. Inductively, $L = L^n$. In particular, if $w \in L^+$ then $w \in L^n$ for some $n$, and so $w \in L$, showing that $L^+ \subseteq L$; and $L \subseteq L^+$ trivially holds.

If $L = L^+$ then we cannot conclude that $L = L^2$. For example, $a^+ = (a^+)^+$ but $a^+ \neq a^+a^+$.

If $L = L^2$ then we cannot conclude that $L = L^*$. For example, $\emptyset = \emptyset^2$ but $\emptyset \neq \emptyset^*$.

However, it is possible to prove the following:

• If $L = L^+$ and $\epsilon \in L$ then $L = L^2$. This shows that if $\epsilon \in L$, then $L = L^+ \Leftrightarrow L = L^2$.
• If $L \neq \emptyset$ then $L = L^2 \Rightarrow L = L^*$. This shows that if $L \neq \emptyset$, then $L = L^* \Leftrightarrow L = L^2$.

Indeed, if $L = L^+$ and $\epsilon \in L$ then $L^2 \subseteq L^+ = L$, and $L \subseteq \epsilon L \subseteq L^2$.

Next, if $L \neq \emptyset$ and $L = L^2$ then let $w$ be a word of smallest length in $L$. Since $L = L^2$, we can write $w = xy$, where $x,y \in L$. By assumption, $|x|=|y|=|w|$, and so $|w| = 2|w|$, implying that $w = \epsilon$. Together with $L^+ \subseteq L$, this shows that $L^* \subseteq L$, and so $L = L^*$.

---

Another nice characterization is: $$ L = L^* \Leftrightarrow L = M^* \text{ for some language } M. $$ One implication is trivial. In the other direction, if $L = M^*$ then $L^* = (M^*)^* = M^* = L$.

This characterization remains true if we impose restrictions on $M$, for example $M \cap M^2 = \emptyset$. Indeed, suppose that $L = L^*$, let $\tilde L = L \setminus \{\epsilon\}$, and let $M = \tilde L \setminus \tilde L^2$. Note that $M^2 \subseteq \tilde L^2$, and so $M \cap M^2 = \emptyset$. Also, clearly $M^* \subseteq \tilde L^* = L$. On the other hand, we can prove inductively that $L \subseteq M^*$.

Indeed, let $w \in L$. If $w = \epsilon$ then clearly $w \in M^*$. Otherwise, $w \in \tilde L$. If $w \in M$ then clearly $w \in M^*$. Otherwise, $w \in \tilde L^2$, that is, $w = xy$, where $|x|,|y| < |w|$. By induction, $x,y \in M^*$, and so $w = xy \in M^*$.