Autômato com pilha determinístico
Na teoria dos autômatos, um autômato com pilha determinístico (APD) é uma variante de autômato com pilha. O APD aceita as linguagens livres de contexto determinística, um subconjunto próprio de linguagens livres de contexto.
Um autômato com pilha "M" (não necessariamente determinístico) pode ser definido com uma 7-upla: M é determinístico se satisfaz ambas as condições: A configuração instantânea de um Autômato com pilha determinístico é dado por uma tripla, a saber: [q,w,p], onde: Há dois critérios de aceitação possíveis: aceitação por "pilha vazia" e aceitação por um "estado final". Os dois não são equivalentes para autômatos com pilha determinísticos (embora sejam para autômatos com pilha não determinísticos). As linguagens aceitas por "pilha vazia" são linguagens que são aceitas pelo "estado final". Não existe nenhuma palavra na linguagem que é prefixo de outra palavra na linguagem.
Seja um APD: M = ( Q , Σ , Γ , q 0 , $ , F , δ ) {\displaystyle M=(Q\,,\Sigma \,,\Gamma \,,q_{0}\,,\$\,,F\,,\delta \,)} , então a linguagem reconhecida por M é: onde ⊢ ∗ {\displaystyle \vdash ^{*}} significa que a mudança ocorre em um número arbitrário de passos, e ⊢ M {\displaystyle \vdash _{M}} representa o autômato M.
Se L ( A ) {\displaystyle L(A)} é uma linguagem aceita pelo AP A {\displaystyle A} , ela pode ser aceita também por um APD se e somente se existe uma única computação de uma configuração inicial até uma aceitação para todas as cadeias pertencentes a L ( A ) {\displaystyle L(A)} . Se L ( A ) {\displaystyle L(A)} pode ser aceita por um AP, ela é uma linguagem livre de contexto, e se ela pode ser aceita por um APD ela é uma linguagem livre de contexto determinística. Nem todas as linguagens livres de contexto são determinísticas. Isto faz de um APD um dispositivo mais fraco que um autômato com pilhas. Por exemplo, a linguagem de palíndromos de mesmo comprimento no alfabeto de 0 e 1 tem a gramática livre de contexto S → 0S0 | 1S1 | ε. Uma cadeia arbitrária desta linguagem não pode ser analisada sem ler todos os seus primeiros símbolos, o que significa que um autômato com pilha tem que tentar transições alternativas entre estados para acomodar os diferentes possíveis comprimentos de uma cadeia não totalmente analisada. O problema geral de decidir se uma linguagem livre de contexto pode ser aceita por um APD é indecidível.
Fechamento
Propriedades de fechamento de linguagens livres de contexto determinísticas (aceitas por um APD pelo estado final de aceitação) são drasticamente diferentes das propriedades das linguagens livres de contexto. Como exemplo, elas são (efetivamente) fechadas sob a operação de complemento, mas não são fechadas sob a operação de união. Provar que o complemento de uma linguagem aceita por um AP é também aceita por um autômato com pilha determinístico é bastante complicado. Em princípio, deve-se evitar infinitas computações. Como consequência da operação de complemento, ela é decidível se um APD aceita todas as palavras sobre seu alfabeto de entrada, testando o seu complemento para a cadeia vazia. Isto não é possível para gramáticas livres de contexto (nem para APs no geral).
Problema de equivalência
Geraud Senizergues provou que o problema de equivalência para autômatos com pilha determinísticos (isto é, dados dois APDs A e B, L(A)=L(B)?) é decidível. Esta prova rendeu-lhe em 2002 um Prêmio Gödel. Para AP não determinísticos, o problema de equivalência é indecidível.
