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

• 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
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