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)$

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

Often, if you want to show that one of multiple conclusions is true, you can assume that all but one are false and show that the last one has to be true.

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-$*$.


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.