Consider the language L = {0^{i}1^{j}2^{j}3^{3i} |
i and j are ≥ 1}. You can show L is context free. It turns out Half(L) is not
context free, but to prove it, it helps to intersect first with a regular language.
Remember that if L were a CFL, then L intersected with any regular language would
also be a CFL. Added 5/5: Actually, if you are clever about how you select z, you
can use the pumping lemma directly on Half(L). You do not have to intersect with a regular
language first.