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

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?

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

• Well, should have searched better...sry for double asking, but thx for answering :) Aug 24, 2020 at 22:53
• Actually, it is an interesting and nontrivial question, and it gives me the opportunity to think to a simple example that I'll certainly use in class (I remebered Yuval's examples, but they are to complex for first year undergraduates). Aug 24, 2020 at 23:01
• Another example suitable for beginners is that over the alphabet $\{ (,)\}$ every string is the concatenation between a well parenthesized string and a non-well parenthesized string. The language of all strings is regular, while the other two are not, and usually undergraduates know that example. Aug 25, 2020 at 1:28

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.