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

## 1 Answer

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.

To elaborate a bit on how to get there: CFLs can express that two numbers are the same, but not that three numbers are the same. So I want the square-root operation to introduce another equality, as it seems predisposed to do so.

• 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
• @bigbang I can't give a definitive answer (we'd first need to formalize what "parameterized with one variable" would mean), but I think you were looking in the wrong place. I've added a bit of an explanation how I found the example. – Arno Apr 29 at 10:03