HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
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.

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.

Context

StackExchange Computer Science Q#139650, answer score: 8

Revisions (0)

No revisions yet.