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

Does there exist a context-free language $L$ such that $L\cap L^2$ is not context-free?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
suchfreecapexistlanguagethatdoescontexttherenot

Problem

I can see that $L$ has to be context-free but not regular here as regular languages are closed under concatenation and intersection. But $L\cap L^2$ looks too weird. I couldn't think of any $L$ that gives rise to meaningful $L\cap L^2$.

Any hint would be appreciated!

Solution

You can take
$$
L = \{ a^n b^n : n \geq 1 \} \cup \{ a^k b^n a^n b^\ell : n,k,\ell \geq 1 \}.
$$
You can check that
$$
L \cap L^2 = \{ a^n b^n a^n b^n : n \geq 1 \}.
$$

Context

StackExchange Computer Science Q#104279, answer score: 3

Revisions (0)

No revisions yet.