Percebo que os autômatos não determinísticos de empilhamento podem ser uma melhoria em relação aos determinísticos, pois eles podem "escolher" entre vários estados e existem algumas linguagens livres de contexto que não podem ser aceitas por um empilhamento determinístico.

Ainda assim, não entendo exatamente como eles "escolhem". Para os palindormes, por exemplo, todas as fontes que encontrei apenas dizem que o autômato "adivinha" o meio da palavra. O que isso significa?

Eu posso pensar em vários significados possíveis:

1. Ele entra em um estado aleatoriamente e, portanto, pode não aceitar uma palavra, que na verdade está no idioma

2. De alguma forma, funciona "de todas as maneiras possíveis"; portanto, se o primeiro estiver errado, ele testa se algum dos outros pode estar certo

3. Existe algum mecanismo que eu não conheço, que escolhe o meio da palavra e, portanto, não é aleatório, mas o autômato sempre encontra o meio certo.
   

Este é apenas um exemplo; o que eu quero saber é como funciona para qualquer autômato que possua vários estados a seguir para um e o mesmo estado antes dele.

Simplesmente, o mecanismo é mágico. A idéia do não-determinismo é que ele simplesmente sabe qual o caminho a seguir para aceitar a palavra, e segue por esse caminho. Se houver várias maneiras, será uma delas.

O não determinismo não pode ser implementado como tal em hardware real. Simulamos usando técnicas como backtracking. Mas é principalmente um dispositivo teórico, que pode ser usado para simplificar a apresentação de certos conceitos.

Para o palíndromo, você pode pensar sobre isso de duas maneiras. Ou existe um poder mágico que permite à sua máquina dizer "este é o meio da palavra, hora de mudar de empurrar para estourar" ou depois de ler cada letra, diz: "Vou abrir um novo processo que esta carta é o meio da palavra e veja se é um palíndromo. Nesse outro segmento, continuarei tentando, assumindo que esse não é o meio da palavra ".

Outra maneira de pensar nisso é como um paralelismo infinito. Portanto, um modelo equivalente seria que, em vez de escolher um novo caminho, ele tente simultaneamente os dois caminhos, ramificando novos "processos", tendo sucesso, se houver algum, em um estado final depois de ler a palavra inteira. Novamente, isso não pode ser construído usando hardware real, mas pode ser modelado com não-determinismo.

O interessante sobre o não-determinismo é que, para autômatos finitos e máquinas de Turing, isso não aumenta seu poder computacional, apenas sua eficiência.

A principal diferença (na minha opinião) entre um autômato determinístico e um autômato não determinístico é que, para um autômato determinístico, uma determinada palavra de entrada possui apenas um caminho através da máquina. Em um autômato não determinístico, uma determinada palavra de entrada pode ter vários caminhos através da máquina (porque pode haver escolha em alguns pontos).

À luz disso, a condição de aceitação de uma palavra de entrada também precisa ser alterada para acomodar o fato de que uma palavra pode induzir vários caminhos através da máquina. A definição usual de aceitação para um autômato não determinístico é a seguinte: Para que uma palavra seja aceita pelo autômato, deve haver pelo menos um caminho de aceitação induzido por essa palavra.

Isso então leva à ideia de um "adivinhação" de autômato, se uma palavra é aceita por um autômato não determinístico, então tendemos a pensar no autômato como fazendo automaticamente as escolhas certas, de modo que (um) caminho (s) de aceitação é seguido quando essa palavra é apresentada como entrada.

O que isso significa para os palíndromos é que o pda terá essencialmente dois modos: um modo de empurrar, onde empurra as letras atuais na pilha e um modo de popping, em que as letras são exibidas e as correspondem à entrada. Esta máquina terá uma transição vazia do estado push para o estado popping que poderá seguir em qualquer ponto da palavra. No entanto, a máquina apenas esvaziará sua pilha e passará para um estado de aceitação se tiver lido um palíndromo e seguido a transição vazia no meio do palíndromo. Como exigimos apenas a existência de um caminho aceitante, podemos dizer que o autômato "adivinha" onde está o meio da palavra.

A idéia de não-determinismo é bastante simples: o autômato pode ter vários próximos passos em determinadas situações. O autômato aceita se houver alguma (pode haver várias!) Sequência de etapas que leva da configuração inicial para a de aceitação, e somente rejeita se não houver essa sequência.

Isso significa que "decide" qual passo a seguir nessas situações ambíguas. Uma maneira de falar sobre isso é dizer que sempre seleciona magicamente o próximo passo "certo" (ou um, se houver vários passos "certos"). Outra maneira de ver é que, em tais situações, o cálculo do autômato se divide em várias cópias, cada uma seguindo um caminho.

Na prática, isso pode ser implementado retornando, colocando algum tipo de tag nos locais onde a decisão foi tomada e volte e tente a próxima alternativa se o caminho atual não der certo. Isso geralmente é tratado por recursão. Ou complementando as informações que o autômato possui "legalmente" com informações extras (é isso que você faz quando mostra como um autômato não-determinístico funciona no quadro-negro, olhando para frente e descobrindo qual das etapas leva ao sucesso).

"Adivinhar" está diretamente relacionado à nossa interpretação existencial do não-determinismo

Em poucas palavras: essa idéia de que um autômato não determinístico pode adivinhar (ou ser ajudado por um oráculo) está diretamente relacionada à nossa interpretação existencial do não determinismo. Outra interpretação é possível (talvez outras) em que "adivinhar" não faria sentido.

O não determinismo é estranho. Temos uma maneira de interpretá-lo na teoria dos autômatos, mas não é a priori óbvio como devemos fazer isso.

Pode parecer surpreendente, mas o não-determinismo é uma situação muito comum. Quando é preciso provar um teorema, dados os axiomas de alguma teoria matemática, o processo é naturalmente não determinístico. É por isso que geralmente não sabemos o que fazer para resolver um problema, por exemplo, para encontrar as soluções de uma equação de terceiro grau ou provar algum teorema.

Existem várias maneiras de combinar o que já é conhecido com as regras de inferência para obter novos resultados. E a situação é geralmente a mesma se tentarmos reconstruir uma prova para trás a partir do resultado.

Ao tentar resolver esse problema, tentamos " adivinhar " um caminho em algum sistema de transição.

Na verdade, não adivinhamos, mas construímos em nossa mente alguma estrutura que organiza e / ou simplifica o labirinto de possibilidades para que possamos ver nosso caminho através dele. Em alguns casos, a pergunta segue um padrão identificado para o qual temos uma maneira padrão de (às vezes? Geralmente? Sempre?) Encontrar uma solução, e chamamos isso de algoritmo.

Uma técnica (geralmente cara) que podemos usar é simplesmente explorar completamente o labirinto: seguir todos os caminhos, fazendo a amplitude primeiro para evitar ser pego em um subgráfico infinito. Isso é praticamente o que está sendo feito, combinando todos os cálculos possíveis de um autômato não determinístico. Essa computação combinada derivada é em si uma determinística.

$DC$$A$$A$$A$

Na verdade, poderia haver diferentes maneiras de interpretar uma computação não determinística . Afaik eles são todos consistentes, mas não um com o outro.

$R$$w$

A idéia de adivinhar para o reconhecedor é apenas uma imagem tirada de nossa própria maneira de "adivinhar" como encontrar essa árvore de provas. Mas a grande diferença é que nossos cérebros não são PDAs. São dispositivos muito mais complexos, com a capacidade de explorar e mapear aproximadamente estruturas de transição, para que possamos encontrar o caminho através delas, o que às vezes consideramos uma suposição.

Essa interpretação da computação não determinística é o que eu chamaria de aceitação existencial , em referência ao fato de exigir apenas a existência de uma única computação de aceitação. Corresponde à parada existencial que apresentei em outra resposta .

No entanto, também se poderia interpretar o não-determinismo de uma maneira universal como: diz-se que um reconhecedor aceita (universalmente) uma entrada "w" se todos os cálculos possíveis pararem e aceitarem a entrada. Essa aceitação universal corresponde ao conceito de parada universal introduzido na mesma resposta.

A aceitação universal e a parada universal parecem levar a um entendimento autoconsistente do não-determinismo. Portanto, alguém poderia fazer um trabalho teórico com essa definição. Mas não é consistente com nossa prática usual em muitas situações não determinísticas, como prova de teoremas, ou na situação da vida cotidiana. Quando confrontados com um problema, queremos apenas uma maneira de resolvê-lo e, em seguida, não nos importamos se outras formas são bem-sucedidas ou não (bem, isso é um pouco mais simplificado).

Se tivermos que reconhecer um palíndromo, podemos adivinhar medindo o comprimento e procurando o meio. O PDA não pode. Mas, como estamos interessados ​​apenas na existência de uma solução, sempre podemos fingir que ela pode ... se isso for útil. Ou podemos considerar que ele possui oráculos fornecidos por máquinas mais inteligentes (nós?) Para ajudá-lo. Ou você pode até chamá-lo de mágica e pensar que é (afinal, o quantificador existencial é uma espécie de varinha mágica). Se puder ajudar, ajudará. Se não houver cálculo aceitável, nenhuma ajuda será útil.

Observe que essa idéia de adivinhação não teria sentido na interpretação da aceitação universal.