Problem Detail: How do you prove that the language of even-lengthed palindromes, i.e., $L=left{ ww^R mid win leftlbrace 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 nge 0 } cup { a^nbba^{2m}bba^n mid m,nge 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
