Excercise from Shallit. Let . Then is not context free.
Contradics the pumping lemma for context free languages.
Proof. Suppose is context-free, then there exists such that for every word with there exists words such that and for every .
Now pick .
Then . Consider any factorization s.t. . We have one of three cases:
1. ends exactly in or at the left of in .
2. or begins at the left of in end ends at the right of in .
3. begins exactly in or at the right of in .
Consider the following values for .
Case 1., pick .
Case 2., pick any .
Case 3. pick any .
Then holds for every case. This contradicts the pumping lemma, thus is not context-free. Q.E.D.