**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.**

Advertisements