How do you prove that the language of even-lengthed palindromes, i.e., $L=\left\{ ww^R \mid w\in \left\lbrace 0,1 \right\}^* \right\}$, can not be accepted by a determinsitc Push-Down-Automaton?

Is there any general way to prove that a context-free language can not be accepted by a deterministic PDA? I mean something like pumping lemma maybe?


1 Answer 1


As Luke notes, there is a Pumping Lemma for deterministic CFL. If there are two strings $zz_1$ and $zz_2$ in the language with common prefix $z$, then for deterministic devices the computation in both substrings $z$ must be the same. The idea behind that Lemma is that now also the pumping must be the same for both strings. In context-free languages pumping is of the form $uvwxy$. The Lemma states that either $vx$ are inside $z$ for both $zz_1$ and $zz_2$ or $v$ is inside $z$ and there are $x_1$ and $x_2$ inside $z_1$ and $z_2$ so we can pump both words that way.

For full details check the Lemma.

Now consider $K = L \cap ( a^*bba^* \cup a^*bba^*bba^* ) = \{ a^nbba^n \mid n\ge 0 \} \cup \{ a^nbba^{2m}bba^n \mid m,n\ge 0 \} $. If $L$ is DCFL then so is $K$. Can we pump $z_1 = a^{2n}bba^{2n}$ and $z_2 = a^{2n}bba^{2n}bba^{2n}$ in the same way? No. The $v,x$ parts are situated differently when we pump for $z_1,z_2$ which contradicts the DCFL Pumping.

Again, one has to be slightly more precise, and quote the proper parts of the Lemma.


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.