patternMinor
Existence of a CFL $L$ such that $\sqrt{L}$ is not CFL
Viewed 0 times
suchcflexistencesqrtthatnot
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#139650, answer score: 8
Revisions (0)
No revisions yet.