Regular composition of non-regular language

Question

I've got the following problem:

Let's take language $L$.

Is it posible that $L$ is not regular itself,
but it's composition $L\cdot L$ becomes regular?

I suspect that's correct, yet I neither found an example of such language
nor can prove the thesis wrong.

Any clues?

Answer 1

Let $L$ be the language of words over the single-element alphabet $\Sigma = \{a\}$ whose length isn't a prime number, i.e. $$ L = \{\alpha^{ab} \,:\; a,b \in \mathbb{N} \setminus \{1\}\} \text{.} $$ $L$ isn't regular, you can verify that e.g. by applying the pumping lemma to the complement of $L$.

Now pick a prime $p > 11$, which is then surely odd. Then $p-9$ is even and $p-9 > 2$ which allows you to write $p$ as $$ p = ab + a'b' \quad\text{where}\quad a=2,\, b = \underbrace{\frac{p-9}{2}}_{\in\mathbb{N}\setminus\{1\}},\, a'=3,\,b'=3 \text{.} $$ It follows that $\alpha^p \in L\cdot L$, and since $\alpha^0 = \epsilon \in L$ means $L \subset L\cdot L$, you get $$ L\cdot L = \Sigma^\star \setminus E $$ where $E$ is some subset of $\{\alpha^1, \alpha^2, \alpha^3, \alpha^5,\alpha^7, \alpha^{11}\}$.

In particular, $E$ is finite, and $L\cdot L$ is therefore regular.

Answer 2

Let $\Sigma = \{1\}$. Let $L$ be a language that contains all even length strings as well as $1$ and any collection of odd length strings. Then $LL= 1^*$, whereas $L$ itself can be complex.