patternMinor
prove no DPDA accepts language of even-lengthed palindromes
Viewed 0 times
acceptspalindromeslanguagedpdaprovelengthedeven
Problem
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?
$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?
Solution
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.
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.
Context
StackExchange Computer Science Q#11598, answer score: 5
Revisions (0)
No revisions yet.