1
$\begingroup$

L is context-free language. Then we make new language L'={x|$\exists$y xy∈L,|x|=|y|}. Is L' context-free or not always? I'm stuck on this problem. I suppose that there are examples when L' isn't context-free, but can't create any.

$\endgroup$
6
$\begingroup$

http://infolab.stanford.edu/~ullman/ialc/spr10/sol/solution4.pdf gives a counterexample:

$$L = \{ 0^i1^j2^j3^{3i}: i,j \ge 1 \}$$

is context free but half($L$) is not. The argument is sketched in the linked PDF.

$\endgroup$
0
$\begingroup$

The proof in the PDF given is missing a lot of important details. Yes, it is a routine exercise to show that $L = \{0^n 1^n 2^n \mid n \geq 0\}$ cannot be pumped, but that doesn't mean a priori that a string $0^n 1^n 2^n$ can't be pumped as a substring of the language $half(\{0^j 1^i 2^i 3^{3j}\})$ (If this were true for any language then $\Sigma^*$ for $|\Sigma| > 2$ wouldn't be context free!).

Instead, consider the CFL generated by $S \to 0S333 \mid 0T44333$ and $T \to 1T2 \mid 12$. This CFL is $0^j 1^i 2^i 44 3^{3j}$ and the intersection with the regular language $0^*1^*2^* 4$ is $\{0^n 1^n 2^n4 \mid n \geq 0\}$ which is evidently not context free.

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