patternMinor
Does there exist a context-free language $L$ such that $L\cap L^2$ is not context-free?
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!
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 \}.
$$
$$
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.