provar que nenhum DPDA aceita linguagem de palíndromos de tamanho uniforme

Como você prova que o idioma dos palíndromos pares, ou seja, , não pode ser aceito por um autômato push-down determinado?$L=\left\{ ww^R \mid w\in \left\lbrace 0,1 \right\}^* \right\}$

Existe alguma maneira geral de provar que uma linguagem livre de contexto não pode ser aceita por um PDA determinístico? Quero dizer algo como bombear lema, talvez?

Como Luke observa, existe um lema de bombeamento para CFL determinística . Se houver duas cordas $zz_1$ e $zz_2$ no idioma com prefixo comum $z$, para dispositivos determinísticos, o cálculo nas duas substrings $z$deve ser o mesmo. A idéia por trás desse lema é que agora também o bombeamento deve ser o mesmo para as duas cordas. Em linguagens sem contexto, o bombeamento é da forma$uvwxy$. O Lemma afirma que ou $vx$ estão dentro $z$para ambos $zz_1$ e $zz_2$ ou $v$ está dentro $z$ e há $x_1$ e $x_2$ dentro $z_1$ e $z_2$ para que possamos bombear as duas palavras dessa maneira.

Para detalhes completos, consulte o Lema.

Agora considere $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 \}$. E se$L$ é DCFL então é $K$. Podemos bombear$z_1 = a^{2n}bba^{2n}$ e $z_2 = a^{2n}bba^{2n}bba^{2n}$do mesmo jeito? Não.$v,x$ as peças estão situadas de maneira diferente quando bombeamos para $z_1,z_2$ o que contradiz o DCFL Pumping.

Novamente, é preciso ser um pouco mais preciso e citar as partes apropriadas do lema.