# If $R\equiv RR$, then $R\equiv \emptyset\text { or } R\equiv \epsilon\text{ or } L(R)\text{ is infinite}$

If $R\equiv RR$, then $R\equiv \emptyset\text { or } R\equiv \epsilon\text{ or } L(R)\text{ is infinite}$

This seems true to me just looking at it.

For example if $R\equiv \emptyset$, then this means $L(R)=L(\emptyset)=\emptyset$

Then $\emptyset\emptyset=\emptyset$, and so we satisfty our assumption that $R\equiv RR$

Similarly, if $R\equiv \epsilon$, then this means $L(R)=L(\epsilon)=\{\epsilon\}$

Then $\{\epsilon\}\{\epsilon\}=\{\epsilon\}$, and so we satisfty our assumption that $R\equiv RR$

Finally, if $L(R)$ is infinite, then this means that $R$ is closed under the Kleene star $*$ operation, and so $RR$ is still just $R$.

So in all cases, it agrees with the assumption.

I'm not sure how to "prove it" though.

How do you prove something of $A\to (B\lor C\lor D)$

• What is $R$? It helps to give context at the top. – Thomas Andrews Aug 2 '17 at 17:31
• Based on the context and tags, I assume it's a regular expression. – platty Aug 2 '17 at 17:48
• yes its a regex – K Split X Aug 2 '17 at 18:24

Here, assume that $R \not\equiv \varnothing$ and $R \not\equiv \{\varepsilon\}$. We show that $L(R)$ must be infinite.
We know that $L(R)$ must contain a nonempty string, call it $w$. Then we also know that $w^k$ satisfies $R^k$. But we have that $R \equiv R^k$ for any $k \in \mathbb{Z}^+$ (by induction, $R^{k+1} \equiv RR^k \equiv RR \equiv R$). Thus, $w^k \in L(R)$ for any $k \in \mathbb{Z}^+$. This shows that our language contains an infinite number of strings, and we are done.
Note that it's not true that $L(R)$ being infinite implies that it is closed under Kleene-$*$. For example, consider $R = ab*$. This contains an infinite number of strings, but is in fact not closed under Kleene-$*$, since every string in the language must contain exactly one $a$. In this case, we are close, since $R \equiv R^k$ for any $k \in \mathbb{Z}^+$, but we don't neccessarily know if this is true for $k = 0$, which is required for closure under Kleene-$*$.