Proving the language $\{w \in \{0, 1\}^{\ast} : w = w^{R}$, $|w|_{0} = |w|_{1} \}$ is not Context Free using Pumping Lemma

Question

$\textit{Proof}$. Let $A$ be the language $\{w \in \{0, 1\}^{\ast} : w = w^{R}$, $|w|_{0} = |w|_{1} \}$. We will use the Pumping Lemma to prove that $A$ is not Context Free Language (CFL). The proof is by contradiction.

Suppose that $A$ is CFL. Let $p$ be the Pumping length given by the Pumping Lemma. Let $s$ be the string $1^{p}0^{p}0^{p}1^{p}$. Since $s \in A$ and $|s| \geq p$, the Pumping Lemma guarantees that $s$ can be divided into five pieces, $=uvxyz$, satisfying the following conditions:

1. for each $i \geq 0$, $uv^{i}xy^{i}z \in A$,
2. $|vy| > 0$
3. $|vxy| \leq p$

Then, by condition 3, we have that $vxy$ is a substring of the first half of $s\ (1^{p}0^{p})$, or $vxy$ is a substring of the middle of $s\ (0^{p}0^{p})$, or $vxy$ is a substring of the second half of $s\ (0^{p}1^{p})$. Let's analyze each case:

1. If $vxy$ is a substring of the first half of $s\ (1^{p}0^{p})$, then, $vxy$ can have only $1's$, or can have both $1's$ and $0's$, or can have only $0's$. Let's analyze each case:
1. If $vxy$ contains only $1's$, then, $uv^{0}xy^{0}z = uxz$ will have less $1's$ than $0's$, thus $uxz \notin A$, and then the condition 1 é violated, therefore we have a contradiction.
2. If $vxy$ contains $1's$ and $0's$, then $uv^{0}xy^{0}z = uxz \neq (uxz)^{R}$, thus $uxz \notin A$, and then the condition 1 é violated, therefore we have a contradiction.
3. If $vxy$ contains only $0's$, then, $uv^{0}xy^{0}z = uxz$ will have less $0's$ than $1's$, thus $uxz \notin A$, and then the condition 1 é violated, therefore we have a contradiction.
2. If $vxy$ is a substring of the middle of $s\ (0^{p}0^{p})$. In this case $vxy$ will have only a kind of symbol, thus, $ uv^{0}xy^{0}z = uxz$ will have less $0's$ than $1's$, thus $uxz \notin A$, and then the condition 1 é violated, therefore we have a contradiction.
3. If $vxy$ is a substring of the second half of $s\ (0^{p}1^{p})$, thus, $vxy$ can have only $0's$, or can have both $0's$ e $1's$, or can have only $1's$. Let's analyze each case:
1. If $vxy$ have only $0's$, then, $uv^{0}xy^{0}z = uxz$ will have less $0's$ than $1's$, thus $uxz \notin A$, and then the condition 1 é violated, therefore we have a contradiction.
2. If $vxy$ have $0's$ and $1's$, then, $uv^{0}xy^{0}z = uxz \neq (uxz)^{R}$, thus $uxz \notin A$, and then the condition 1 é violated, therefore we have a contradiction.
3. If $vxy$ have only $1's$, then, $uv^{0}xy^{0}z = uxz$ will have less $1's$ than $0's$, thus $uxz \notin A$, and then the condition 1 é violated, therefore we have a contradiction.

Since we analyzed all possible cases and in all cases a contradiction was inevitable, then we can conclude that $A$ is not CFL. $\square$

I tried to cover all possible cases. But I am not so sure this is correct or if it can be further simplified.

Answer 1

It’s correct and clear, but it could be simplified. There are really just two cases.

• If $vxy$ contains only zeroes or only ones, pumping in either direction will produce a word $w$ such that $|w|_0\ne|w|_1$.
• If $vxy$ contains both zeroes and ones, then it intersects only one of the two blocks of ones in $s$, and pumping in either direction will produce a word $w$ such that $w\ne w^R$.