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

135 Views Asked by At

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

1

There are 1 best solutions below

0
On BEST ANSWER

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