3
$\begingroup$

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.

$\endgroup$
1
7
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ – bigbang Apr 28 at 18:42
  • $\begingroup$ @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 \}$. $\endgroup$ – Hendrik Jan Apr 28 at 19:43
  • $\begingroup$ @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. $\endgroup$ – Arno Apr 29 at 10:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.