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.
[Math] Is language, made of the first half of the words from context-free language, context-free
context-free-grammarformal-languages
Related Question
- [Math] Subtracting a context-free language from a regular language
- [Math] Is it possible for a subset of a non-context free language to be context-free
- [Math] Example of context-free but non regular language with context-free complement
- Proof Attempt: non Context free languages and non regular language with some words added stay non regular/context-free.
Best Answer
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.