# Existence of a CFL $L$ such that $\sqrt{L}$ is not CFL

Does there exist a CFL L such that the language defined as $$L' = \sqrt{L} = \{w | ww \in L\}$$ is not CFL? I feel that there is no such $$L$$ but obviously, I am unable to prove it.

I am sorry but I have not made any mentionable progress with my attempts on this problem.

I would appreciate any hint to the proof or a language $$L$$ that could satisfy this.

There is an example, and $$L = \{a^nb^na^{2m}b^ka^k \mid n,m,k \in \mathbb{N}\}$$ does the trick. We get that $$\sqrt{L} = \{a^nb^na^n \mid n \in \mathbb{N}\}$$, which is a standard example of a non-context-free language.
• Amazing! Thanks so much. Is it possible to create an example parametrized with one variable, say $n$? I had been trying to solve this problem using such languages only which is why I couldn't find one probably. – bigbang Apr 28 at 18:42
• @bigbang Close $\{ a^nb^n \mid n\in \mathbb N \} \cdot \{ a^na^n \mid n\in \mathbb N \} \cdot \{ b^na^n \mid n\in \mathbb N \}$. – Hendrik Jan Apr 28 at 19:43