prove that set of palindroms such that $\#_0(w)=\#_1(w)$ is not CFG

Question

$B$ - set of palindroms such that number of $1s$ is equal to number of $0s$. Every palindrom $\in \{0,1\}^*$
And my task let me that $B$ is not CFG. But I don't agree with it.
Because of the fact that $\#_0(w)=\#_1(w)$ I conlude that $B$ is set of palindroms such that their length is even, so:
$B=\{ww^r|w\in \{0,1\}^*\}$
A show CFG for this language $B$:
$S\rightarrow 1S1|0S0|\epsilon$
What's up my dear friends ?

Answer 1

Hint:

• For example $10111101$ is a palindrome of even length with different number of zeros and ones.
• Intersecting $B$ with regular language $1^*0^*1^*$ gives you $\{1^n0^{2n}1^n\mid n\in \mathbb{N}\}$.
• The above is quite similar to $\{a^nb^nc^n\mid n\in \mathbb{N}\}$ which is not context-free.

I hope thos helps $\ddot\smile$

Answer 2

The context free grammar you're given does not correspond to the definition of $B$ because $11$ is generated by grammar but it's not an element of $B$. Actually the definition meant by the question is : $$B=\{ww^r|w\in \{0,1\}^*,|w|_1=|w|_0\}$$ which is more complicated but can be done using the pumping Lemma, the idea behind the proof:

We choose a palindrome with $2p$ $1$’s and $2p$ $0$’s such that the $1$’s are all at the middle. We pump it by deleting the repeated strings. Because there are so many $1$s, the deleted strings cannot have $0$s from both side, so they either take $0$s from one side and leave the string asymmetric or take only $1$s and leave the string with an unequal amount of $0$s and $1$s.