Autômato com pilha determinístico

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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ísticas,um subconjunto próprio de linguagens livres de contexto.[1]

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 susbtituir 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[editar | editar código-fonte]

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\ge0\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[editar | editar código-fonte]

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[editar | editar código-fonte]

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. [2] O problema geral de decidir se uma linguagem livre de contexto pode ser aceita por um APD é indecidível.[3]

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

Propriedades[editar | editar código-fonte]

Fechamento[editar | editar código-fonte]

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[editar | editar código-fonte]

Geraud Senizergues (1997) 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.[5] Esta prova rendeu-lhe em 2002 um Gödel Prize. Para AP não determinísticos, o problema de equivalência é indecidível.

Notas[editar | editar código-fonte]

  1. Michael Sipser. Introduction to the Theory of Computation. [S.l.]: PWS Publishing, 1997. p. 102. ISBN 0-534-94728-X
  2. Hopcroft, John; Rajeev Motwani & Jeffrey Ullman. Introduction to automata theory, languages, and computation 2nd edition. [S.l.]: Addison-Wesley, 2001. 249–253 pp.
  3. Greibnach, Sheila. (October 1966). "The Unsolvability of the Recognition of Linear Context-Free Languages" 13 (4).
  4. doi:10.1007/BF01946814
    Esta citação será automaticamente completada em poucos minutos. Você pode furar a fila ou completar manualmente
  5. Sénizergues, Géraud. (1997). "The equivalence problem for deterministic pushdown automata is decidable". AUTOMATA, LANGUAGES AND PROGRAMMING 1256/1997: 671–681. DOI:10.1007/3-540-63165-8_221.

Referências[editar | editar código-fonte]

Leitura complementar[editar | editar código-fonte]