# Prove or disprove: $L^2$ context free implies $L$ is context free.

Clearly we have to disprove this. But I am finding it hard to prove it. I was trying in following way:
Considering any non context free language $L$. I was trying to prove that $L^2$ is context free which will contradict given statement. But I don't know to how to prove it. Because by pumping lemma we can show only that language is not CFL but converse is not true.

Can you please help me? Or is there any other way to prove it?

• What is $L^2{}$? – Mariano Suárez-Álvarez Nov 30 '14 at 22:20
• I'd assume that $L^2 = \{ww : w\in L\}$. – Math1000 Nov 30 '14 at 22:25
• Well, since also $\{uv:u,v\in L\}$ is a quite sensible interpretation, we'll have to wait for the OP to tell us what he meant! – Mariano Suárez-Álvarez Dec 2 '14 at 7:31
• @math1000 There is no ambiguity, since $L^2 = LL$, as in any monoid. Thus the interpretation of mariano-suárez-alvarez is the right one. – J.-E. Pin Feb 1 '16 at 17:18

## 1 Answer

The answer is negative, even on a single letter alphabet $\{a\}$. Let $S$ be a non recursively enumerable subset of $\mathbb{N}$ and let $$L = 1 \cup (aa)^*a \cup \{a^{2n} \mid n \in S \}$$ Then $L^2 = a^*$ and thus $L$ is regular, but $L$ is not recursively enumerable (an in particular not context free).

• but the use of a non recursively enumerable subset of $\mathbb{N}$ is tedious. is there an example of a context-sensitive (but recursively enumerable) $L$ for which $L^2$ is context-free ? under the Goldbach conjecture $\{a^p, p \ \ \text{is prime}\}$ would work – reuns Feb 1 '16 at 17:45
• @user1952009 It suffices to modify my example as follows: $L = 1 \cup (aa)^*a \cup \{a^{2p} \mid p \text{ is prime} \}$. Again $L^2 = a^*$, but $L$ is context-sensitive, and not context-free. – J.-E. Pin Feb 1 '16 at 17:49