Como eu mostro que se um PDA aceita alguma string é indecidível?

Como mostro que o problema de decidir se um PDA aceita alguma sequência do formato é indecidível?$\{ w!w \mid w \in \{ 0, 1 \}^*\}$

Tentei reduzir esse problema a outro indecidível, como se duas gramáticas livres de contexto aceitam o mesmo idioma. No entanto, não tenho certeza de como usá-lo como uma sub-rotina.

Aqui está minha abordagem: mostrarei que, se você puder decidir seu problema, poderá decidir o problema de correspondência de Post (PCP), que é conhecido por não ser decidível.

Lembre-se, PCP é um problema de decisão que pergunta se em um conjunto de $2$-tuplos $P=\{(x_1,y_1),\ldots,(x_n,y_n)\}$ você pode construir uma sequência (incluindo repetição) de forma que a concatenada $x_i$se concatenados $y_i$s desta sequência formam a mesma palavra. Observe que o alfabeto precisa ter pelo menos 2 caracteres.

Então deixe $P$ser uma instância do PCP. Considere a seguinte gramática livre de contexto, onde introduzimos um novo símbolo de terminal$t_i$ para o $i$-ésimo elemento em $P$. A gramática tem as seguintes regras:

Obviamente, dada qualquer gramática, podemos encontrar um PDA correspondente que aceite o mesmo idioma da gramática. Portanto, construa o PDA correspondente e use o algoritmo hipotético do seu problema para determinar se esse PDA aceita qualquer palavra da forma$u!v$ (ou seja, se alguém pode derivar qualquer palavra da forma $u!v$desta gramática). Vou mostrar como usar essas informações para resolver a instância do PCP$P$.

Suponha agora que $u!v$é uma palavra nesta gramática. A palavra$u$ possui duas partes, o sufixo, consistindo no $t_i$terminais eo restante chamado prefixo. O mesmo vale para$v$. Nós temos$u=v$se e somente se seus prefixos e sufixos coincidirem. Os sufixos coincidem apenas se tivermos usado a mesma sequência de tuplas de$P$ para construir as palavras $u$ e $v$. Os prefixos de$u$ e $v$ coincidir se a concatenação do $x_i$areia $y_i$s (com base na sequência de tupla invertida fornecida pelo $t_i$s) é o mesmo. Conseqüentemente$u=v$ se e somente se houver uma solução para a instância PCP $P$.

Da mesma forma, se houver uma solução para a instância PCP $P$, então, a partir da solução, é fácil construir uma palavra da forma $u!v$ que é derivável dessa gramática.

Daqui resulta que a instância PCP $P$ tem uma solução se e somente se esta gramática contiver uma palavra no formato $u!v$. Se houvesse um algoritmo para decidir seu problema, poderíamos usá-lo para resolver o PCP. Mas é claro que o PCP é indecidível, então seu problema também é indecidível.

A abordagem pode ser a seguinte. Tente criar uma linguagem sem contexto (= PDA) que codifique as etapas de computação de uma TM, para que a computação completa seja bem-sucedida se houver uma palavra do formulário que você descreve.

Primeiro, você precisa codificar configurações separadas: conteúdo da fita + estado + cabeçalho da posição (você verá isso para equivalência gramatical). Uma linguagem livre de contexto pode codificar uma única etapa$C\vdash C'$ de uma computação, desde que você use imagem espelhada $C\#m(C')$, Onde $m(C)$denota a imagem espelhada (reversão) de $$ C $. (Sou desleixado aqui: talvez seja necessário distinguir a configuração e sua descrição.)

Agora considere o idioma das etapas separadas, concatenadas com o idioma das configurações duplicadas: $C_0\#C_1\#m(C_2)\#C_3\#m(C_4)\# \dots C_{2n-1}\#m(C_{2n})\#C_f!$ $C'_1\#m(C'_1)\#C'_2\#m(C'_2)\#\dots C'_{n+1}\#m(C'_{n+1})$ com para cada $k$, $C_{2k-1} \vdash (C_{2k})$. Isso é livre de contexto, além de código$C_0$ como inicial e $C_f$ como configurações finais.

Agora, a primeira parte garante que temos etapas consecutivas, a segunda parte de que configurações sucessivas são iguais. Se ambas as partes corresponderem, temos um cálculo. O que não podemos decidir.

Essa é a ideia. Posso ter alguns índices incorretos, e toda a sequência deve ser codificada em binário, mas isso pode ser resolvido.