# Let P be the language of palindromes over the alphabet Σ = {0, 1}. and let P‘ be the subset of the palindromes with different numbers of 0s and 1s

Let P be the language of palindromes over the alphabet Σ = {0, 1}. and let P‘ be the subset of the palindromes with different numbers of 0s and 1s. Is P' context-free? I know that for the language of the set of palindromes with the same numbers of 0s and 1s is not context-free.

Intuitively you cannot check palindromicity and (un)equality of numbers using a single pushdown, so also $$P'$$ must be non-context-free.
Formally proving unequal-repeating-numbers to be non-context-free is quite a challenge, see How to prove L := { a^n b^n c^m | n,m >= 0 & n != m } is not context-free? for the language $$\{ a^nb^nc^m \mid n\neq m \}$$. For that language one needs a special $$p!$$ trick, as well as Ogden, a stronger form of the classical pumping lemma.
If one intersects your language $$P'$$ of strings that are palindromes and have unequal numbers of $$0,1$$ with $$0^*(11)^*0^*$$ one obtains the language $$\{ 0^m 1^{2n} 0^m \mid m\neq n \}$$. It seems reasonable to attack that language with similar methods. Then it would follow that $$P'$$ itself is not context-free as context-free languages are closed under intersection with regular languages.
• It would be nice to have such a more elementary proof. We have $P = P'\cup P''$, where $P',P''$ have unequal, equal number of $0,1$. Then $P$ is context-free and you claim that $P''$ is not context-free. I cannot conclude that $P'$ is non-context-free, but perhaps I am overlooking some simple argument. Oct 18 at 0:21