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.

As transições da máquina são baseadas no estado atual e no símbolo de entrada, e também do símbolo mais alto na pilha. Os símbolos mais inferiores na pilha não estão visíveis e não provocam efeitos imediatos. As ações da máquina incluem colocar símbolo na pilha, retirá-lo da pilha ou substituir o topo da pilha. Um autômato com pilha determinístico tem no máximo uma transição possível para uma mesma combinação de símbolo de entrada, estado e símbolo no topo da pilha. Isto é o que o difere de um autômato com pilha não determinístico.

Definição formal

Um autômato com pilha "M" (não necessariamente determinístico) pode ser definido com uma 7-upla:

$M=(Q\,,\Sigma \,,\Gamma \,,q_{0}\,,\$\,,F\,,\delta \,)$

onde

• $Q\,$ é o conjunto finito de estados
• $\Sigma \,$ é o conjunto finito de símbolos de entrada (ou alfabeto de entrada)
• $\Gamma \,$ é o conjunto finito de símbolos da pilha (ou alfabeto da pilha)
• $q_{0}\,\in Q\,$ é o estado inicial
• $\$\,\in \Gamma \,$ é o símbolo inicial da pilha
• $F\,\subseteq Q\,$, onde $F$ é o conjunto de estados de aceitação
• $\delta \,$ é uma função de transição, onde

$\delta \colon (Q\,\times (\Sigma \,\cup \left\{\varepsilon \,\right\})\times \Gamma \,)\longrightarrow {\mathcal {P}}(Q\times \Gamma ^{*})$

onde $\Gamma ^{*}$ representa $\{a_{1}a_{2}...a_{n}|n\geq 0\wedge \forall i.a_{i}\in \Gamma \}$, "o conjunto de todas as cadeias finitas (incluindo a cadeia vazia $\varepsilon$) de elementos de $\Gamma$", $\varepsilon$ representa a cadeia vazia, e ${\mathcal {P}}(X)$ é o conjunto das partes de um conjunto $X$.

M é determinístico se satisfaz ambas as condições:

• Para algum $q\in Q,a\in \Sigma \cup \left\{\varepsilon \right\},x\in \Gamma$, o conjuntos $\delta (q,a,x)\,$ tem no máximo um elemento.
• Para algum $q\in Q,x\in \Gamma$, se $\delta (q,\varepsilon ,x)\not =\emptyset \,$, então $\delta \left(q,a,x\right)=\emptyset$ para todo $a\in \Sigma .$

A configuração instantânea de um Autômato com pilha determinístico é dado por uma tripla, a saber: [q,w,p], onde:

• $q\,\in Q\,$ é o estado atual;
• $w\,$ é a string de entrada
• $p\,$ é a string de pilha (topo -> corpo da pilha)

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.

Linguagem reconhecida por um APD

Seja um APD: $M=(Q\,,\Sigma \,,\Gamma \,,q_{0}\,,\$\,,F\,,\delta \,)$, então a linguagem reconhecida por M é:

$L(M)=\{w\in \Sigma ^{*}\ |[q_{0},w,\varepsilon ]\vdash _{M}^{*}\ [q_{i},\varepsilon ,\varepsilon ],q_{i}\in F\}$.

onde $\vdash ^{*}$ significa que a mudança ocorre em um número arbitrário de passos, e $\vdash _{M}$ representa o autômato M.

Reconhecedores de linguagem

Se $L(A)$ é uma linguagem aceita pelo AP $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)$. Se $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.

Restringir o APD a um único estado reduz a classe de linguagens aceitas pelas linguagens LL(1). No caso de um AP, esta restrição não tem efeito na classe das linguagens aceitas.

Propriedades

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.

Leitura complementar

• Hamburger, Henry; Dana Richards (2002). Logic and Language Models for Computer Science. Upper Saddle River, NJ 07458: Prentice Hall. pp. 284–331. ISBN 0-13-065487-6