[Solved]: prove no DPDA accepts language of even-lengthed palindromes

Problem Detail: 

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?

Asked By : Untitled

Answered By : Hendrik Jan

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11598