0
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ Oct 17, 2023 at 20:03
  • $\begingroup$ 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. $\endgroup$ Oct 18, 2023 at 0:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.