Proof that L^2 is regular => L is regular

Question

I'm trying to show $L^2 \in \mathsf{REG} \implies L \in \mathsf{REG}$ with $L^2 = \{w = w_1w_2 \mid w_1, w_2 \in L\}$ but I cant seem to find a proof that feels right.

I first tryed to show $L \in \mathsf{REG} \implies L^2 \in \mathsf{REG}$, by constructing an machine $M$ that consists of two machines $A=A'$ with $A$ recognizing $L$. $M$ has the same start states as $A$ but the final states of $A$ are put together with the starting states of $A'$. Further $M$ uses the same accepting states as $A'$. Hope that makes sens so far :D

Now to show $L^2 \in \mathsf{REG} \implies L \in \mathsf{REG}$ I'd argue the same way, but:

The machine $M'$ that accepts $L^2$ has to recognize $w_i \in L$ in some way, and because $L^2$ is regular, $M'$ has to be a NFA/DFA. So the machine has to check if $w_i \in L$ and this cant be done by using something else than a NFA/DFA.

This feels wrong and not very mathematical, so maybe somebody knows how to do this?

Answer 1

Your claim is false. Indeed, it is equivalent to prove that if a language $L$ is not regular, then also $L^2$ is not regular, but this is not true. Here Yuval Filmus gives (possibly) two examples of a non regular language whose "square" is regular, namely $L = \{ 1^p \mid p \text{ is an odd prime}\}$, under the Goldbach conjecture, and $L' = \{ 1^{a^2} \mid a \geq 0 \}^2=\{1^n \mid n \text{ is the sum of two squares}\}$.

---

For a simpler example, consider the set

$$\text{NP}=\{1^n\mid n \text{ is not prime}\}$$

Clearly NP is not regular (otherwise also its complementary would be regular), but NP$^2$ is regular, as its complementary is finite. Indeed, if $n$ is even and greater than or equal to 8, then $n=4+(n-4)$ and $4$ and $n-4$ are not prime and so $1^n\in \text{NP}^2$. Instead, if $n$ is odd and greater than or equal to 13, then $n=9+(n-9)$ and $9$ and $n-9$ are not prime, as $n-9$ is even and greater than 2, and again $1^n\in \text{NP}^2$ (actually, NP$^2=\{1^n\mid n\neq 3\}$, here I don't consider 1 as a prime number).

---

In general, if $L$ is a non regular language sufficiently "sparse", then there is a good chance that $(L^C)(L^C)$ is cofinite, and then regular. For example, again on a unary alphabet, one can consider the non regular language

$$\text{L}=\{1^n\mid n \text{ is not a power of }2\},$$

then it is easy to see that $L^2=\{1^n\mid n\not\in\{1,2 \}\}$, which is regular.

On a two letter alphabet one can consider the example below of Bernardo Subercaseaux (I think there's a little misunderstanding in his comment, as here we are considering the concatenation of a non regular language with itself), namely the language $L$ that is the complement of the language of well parenthesized strings on the alphabet $\{(,)\}$: in this case $L^2=\{(,)\}^*\setminus\{\varepsilon,(,)\}$, again regular.

Another simple example is given by the non regular language

$$\text{L}=\{w\in\{a,b\}^*\mid w \text{ is not of the form }a^nb^n\text{ with }n>0\},$$

then it is easy to see that $L^2=\{a,b\}^*$: indeed if $w\in L$, then $w=w\varepsilon\in L^2$, else if $w=a^nb^n$ then $w=a\cdot a^{n-1}b^n\in L^2$.

Answer 2

Here is a simple example. Take any non-regular language $N$ contained in $(aa)^+$ and consider the language $L = 1 + a(aa)^* + N$. Then $L$ is not regular since $L \cap (aa)^+ = N$ is not regular. On the other hand, $L^2 = a^*$ is regular.