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

• Thank you! I think this is a good way of proofing. Is there any way to do the proof without Ogden, perhaps just using the pumping lemma and intersecting/union of two languages? Oct 17, 2023 at 20:03
• 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, 2023 at 0:21