4
$\begingroup$

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!

$\endgroup$
3
$\begingroup$

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 \}. $$

$\endgroup$
2
$\begingroup$

The intersection of the form $L\cap L^2$ actually turns out to be quite powerful. In fact languages like this can code Turing machine computations.

Let $L_1, L_2 \subseteq\{a,b\}^*$ and let $\#$ be a third "special" symbol. Consider $L = L_1\# \cup L_2\#\#$. The only strings in $L\cap L^2$ must end in $\#\#$, and before that must be a string in $L_1\cap L_2$.

Now one can do weird things indeed. Let $L = \{a^nb^{2n}\mid n\ge 1\}^*a^*\# \cup a^1\{b^na^n\}^*\#\#$. Then $L\cap L^2$ consists of strings of the form $a^1b^2a^2b^4a^4\dots b^{2^k}a^{2^k}\#\#$.

$\endgroup$

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.