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

8

Como mostro que o problema de decidir se um PDA aceita alguma sequência do formato é indecidível?{w!ww{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.

David Faux
fonte

Respostas:

12

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={(x1,y1),,(xn,yn)} você pode construir uma sequência (incluindo repetição) de forma que a concatenada xise concatenados yis desta sequência formam a mesma palavra. Observe que o alfabeto precisa ter pelo menos 2 caracteres.

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

SX!YXx1Xt1x2Xt2xnXtnXx1Xt1x2Xt2xnXtnεYy1Yt1y2Yt2ynYtnε
(A variável X está lá apenas para descartar S!)

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 formau!v (ou seja, se alguém pode derivar qualquer palavra da forma u!vdesta gramática). Vou mostrar como usar essas informações para resolver a instância do PCPP.

Suponha agora que u!vé uma palavra nesta gramática. A palavrau possui duas partes, o sufixo, consistindo no titerminais eo restante chamado prefixo. O mesmo vale parav. Nós temosu=vse e somente se seus prefixos e sufixos coincidirem. Os sufixos coincidem apenas se tivermos usado a mesma sequência de tuplas deP para construir as palavras u e v. Os prefixos deu e v coincidir se a concatenação do xiareia yis (com base na sequência de tupla invertida fornecida pelo tis) é o mesmo. Conseqüentementeu=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.Schulz
fonte
1
Agradável! Bem, definitivamente mais direto do que minha própria solução. 1
Hendrik Jan
1
Acho difícil acompanhar o fluxo desta resposta. Por que você argumenta sobre a existência de PDA / gramática no terceiro parágrafo? Se eu leio corretamente, você deseja mapear instâncias do PCP para gramáticas, reduzindo assim a questão de saber se o PCP é decidível. Para esse fim, você também deve mostrar o verso do último parágrafo, ou seja, se não houver u!ufor aceito, o PCP não tem solução. (Bom truque com oti, a propósito.)
Raphael
@ Rafael, eu editei a resposta para abordar o seu comentário. Bons pontos - obrigado!
DW
5

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 etapaCC 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: C0#C1#m(C2)#C3#m(C4)#C2n1#m(C2n)#Cf! C1#m(C1)#C2#m(C2)#Cn+1#m(Cn+1) com para cada k, C2k1(C2k). Isso é livre de contexto, além de códigoC0 como inicial e Cf 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.

Hendrik Jan
fonte
OK eu entendi. No entanto, a parte "Agora considere o idioma de etapas separadas, concatenadas com o idioma de configurações duplicadas ..." pode se beneficiar de mais explicações. Por exemplo, você pode usar os índices corretos. Enfim, é uma boa ideia.
A.Schulz