[Math] Show that the following language is not context free by using the pumping lemma

Question

Let B be the language of all palindromes over $\{0,1\}$ containing equal number of 0s and 1s. Show that B is not context free.

Attempt: I plan to show the string $0^p1^p1^p0^p$ can't be pumped. But the problem is that if we pick v= x 1s and y= x 1s then $uv^ixy^iz \in B$ for any $i$ except for $i=0$. My question is, when we choose a word, do we have to show it can't be pumped in any way? or we have to show that for each case (in this case v and y just contain 1's), there exists a way it can't be pumped?.

Answer 1

The pumping lemma says:

There is a pumping length $p$ such that for every sufficiently long word in the language there is a qualifying decomposition of that word such that for every $n$, this decomposition pumped $n$ times in in the language.

When you want to prove that $B$ is not context free, you need to argue that the pumping lemma property is false for $B$, so you have to negate the description above. This produces

For every pumping length $p$ there is a (sufficiently long) word in the language such that for every qualifying decomposition of that word there is an $n$ such that the decomposition can not be pumped $n$ times.

which is what you have to prove.

In order to prove such a multiply-quantified claim you get to choose everything marked up with "there is", whereas your enemy chooses things marked up with "for every" and you have to be prepared to response no matter what he comes up with.

Thus,

• First the enemy chooses a $p$.
• Then you choose a word $w$ of at least $p$ symbols.
• The enemy decides how to split your word as $w=uvxyz$, following the rules of the lemma.
• After seeing this decomposition you must give an $n$, such that ...
• $uv^nxy^nz$ is not in the language.

So you don't get to choose how to split $0^p1^{2p}0^p$ into five parts. You have to argue that no matter how this splitting is done (as long as $|vxy|\le p$, etc), it will not be pumpable.