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.
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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.
-
$\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 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 at 0:21