Autômato com pilha

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

Na teoria dos autômatos, um autômato com pilha é um autômato finito com uma memória auxiliar em forma de pilha.

Operação[editar | editar código-fonte]

Autômatos com pilha diferem da definição normal de máquinas de estados finitos de duas maneiras:

  1. Eles podem fazer uso da informação que está no topo da pilha para decidir qual transição deve ser efetuada;
  2. Eles podem manipular a pilha ao efetuar uma transição.

Autômatos com pilha escolhem uma transição analisando o símbolo atual na cadeia de entrada, o estado atual e o topo da pilha. Máquinas de estados finitos convencionais apenas analisam o símbolo na cadeia de entrada e o estado atual. Autômatos com pilha adicionam a pilha como recurso auxiliar, deste modo, dado um símbolo da cadeia de entrada, o estado atual e um símbolo no topo da pilha, uma transição é selecionada.

Máquinas de estados finitos apenas escolhem um novo estado como resultado da sua transição, já os autômatos com pilha também podem manipular a pilha, como resultado de sua transição. A manipulação é feita através do desempilhamento de um símbolo da pilha ou através do empilhamento de um novo símbolo ao topo da mesma. Alternativamente, um autômato com pilha pode ignorar a pilha e deixá-la como está.

Os autômatos com pilha compreendem a classe das linguagens livres de contexto, de acordo com a Hierarquia de Chomsky e, portanto, são modelos de computação equivalentes às gramáticas livres de contexto.

Um autômato finito com acesso a duas pilhas possui capacidade de computação equivalente ao de uma máquina de Turing.[carece de fontes?]

Definição formal[editar | editar código-fonte]

Um autômato de pilha é formalmente definido por uma 6-tupla:

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

Onde:

  • \, Q é um conjunto finito de estados.
  • \,\Sigma é um conjunto finito de símbolos, denominado alfabeto de entrada.
  • \,\Gamma é um conjunto finito de símbolos, denominado alfabeto da pilha.
  • \,\Delta\subseteq (Q \times \Sigma^* \times \Gamma^*) \times (Q \times \Gamma^*) é a relação de transição.
  • \,q_{0}\in\, Q é o estado inicial.
  • F\subseteq Q é o conjunto de estados finais (ou de aceitação).

Um elemento (p,a,α,q,β) é uma transição de M. Ela significa que M, estando no estado p, com o símbolo a na cadeia de entrada e com o símbolo α no topo da pilha, pode consumir o símbolo a, transitar para o estado q e desempilhar α substituindo-o por β. O ∑* e o Γ* denotam o fecho de Kleene do alfabeto de entrada e da pilha, respectivamente. Portanto, estes componentes são utilizados para formalizar que o autômato de pilha pode consumir qualquer quantidade de símbolos da cadeia de entrada e da pilha.

Computações[editar | editar código-fonte]

Um passo do autômato com pilha.

A fim de formalizar a descrição semântica dos autômatos com pilha, introduziremos uma descrição da situação atual. Qualquer 3-upla (p,w,\beta) \in Q \times \Sigma^* \times \Gamma^* é chamada de uma descrição instantânea (ID) de M, que inclui o estado atual, a parta da cadeia de entrada que ainda não foi lida e o conteúdo da memória (o cabeçalho é escrito primeiro). A função de transição \delta define a relação origina \vdash_{M} de M na descrição instantânea (ID). Para instruções (p,a,A,q,\alpha) \in \delta existe um passo (p,ax,A\gamma) \vdash_{M} (q,x,\alpha\gamma), para todo x\in\Sigma^* e todo \gamma\in \Gamma^*.

Em geral, autômatos com pilha são não determinísticos, o que significa dizer que dada uma descrição instantânea (p,w,\beta) podem haver diversos passos possíveis. Qualquer um desses passos pode ser escolhido durante uma computação. Com a definição acima, em cada passo um símbolo único (localizado no topo da pilha) é retirado e substituído por quantos símbolos forem necessário. Como consequência, nenhum passo é definido quando a pilha está vazia.

Computações dos autômatos com pilha são sequências de passos. A computação começa no estado inicial q_{0}com o símbolo inicial da pilha Z na pilha e uma cadeia w na fita de entrada e, portanto, com a descrição inicial (q_{0},w,Z). Há duas maneiras de aceitar: O autômato com pilha aceita tanto por estado final, o que significa que depois de ler sua entrada, o autômato atinge um estado de aceitação (in F), quanto por pilha vazia (\varepsilon), o que significa que após ler a cadeia de entrada, o autômato esvazia sua pilha. O primeiro modo de aceitação usa a memória interna, os estados, e o segundo modo a memória externa, a pilha.

Definição formal:

  1. L(M) = \{ w\in\Sigma^* | (q_{0},w,Z) \vdash_M^* (f,\varepsilon,\gamma) com f \in F e \gamma \in \Gamma^* \} (Estado final)
  2. N(M) = \{ w\in\Sigma^* | (q_{0},w,Z) \vdash_M^* (q,\varepsilon,\varepsilon) com q \in Q \} (Pilha vazia)

Aqui \vdash_M^* representa os fechos reflexivos e transitivos da relação origina\vdash_M significando qualquer número de passos consecutivos (zero, um ou mais).

Para cada único autômato com pilha, essas duas linguagens não devem ter relação: eles podem ser iguais, mas normalmente não é o caso. Uma especificação do autômato deve também incluir o modo de aceitação pretendido. Entretanto, todos as condições de aceitação de um autômato com pilha definem uma mesma família de linguagem

Teorema Para todo autômato com pilha M é possível construir um outro autômato com pilha M' tal que L(M)=N(M'), e vice versa, para cada autômato com pilha M é possível construir um autômato com pilha M' tal que N(M)=L(M')

Exemplo[editar | editar código-fonte]

A seguir é a descrição formal do AP, que reconhece a linguagem \{0^n1^n \mid n \ge 0 \} por estado final:

AP para \{0^n1^n \mid n \ge 0\} (por estado final).

M=(Q,\  \Sigma,\  \Gamma,\  \delta, \ p,\ Z, \ F), onde

Q = \{ p,q,r \}

\Sigma = \{0, 1\}

\Gamma = \{A, Z\}

F = \{r\}

\delta consiste nas seis instruções seguintes:

(p,0,Z,p,AZ), (p,0,A,p,AA), (p,\epsilon,Z,q,Z), (p,\epsilon,A,q,A), (q,1,A,q,\epsilon), e (q,\epsilon,Z,r,Z).

Ou seja, no estado p para cada símbolo 0 que for lido, um A é colocado na pilha. Empilhar um símbolo A no topo de um outro A é formalizado como trocar o símbolo A por AA. No estado q, para cada símbolo 1 lido, um A a é desempilhado. Em um outro momento, o autômato se move do estado p para o estado q, enquanto ele pode mover do estado q para o estado de aceitação r somente quando a pilha possuir um único Z.

Representamos a instrução (p,a,A,q,\alpha) como uma ponte que sai do estado p para o estado q rotulada por a; A/\alpha (leia a; substitui A por \alpha).

Entendendo o processo de computação[editar | editar código-fonte]

Computação de aceitação para 0011

A seguir ilustramos como o AP acima computa sobre diferentes cadeias de entrada.

(a) Cadeia de entrada = 0011. Há várias computações, dependendo do momento em que é feita a mudança do estado p para o estado q. Apenas uma dessas computações aceita.

(i) (p,0011,Z) \vdash (q,0011,Z) \vdash (r,0011,Z). O estado final é o de aceitação, mas a entrada não é aceita pois a cadeia não terminou de ser lida completamente.
(ii) (p,0011,Z) \vdash (p,011,AZ) \vdash (q,011,AZ). Não há mais estados possíveis..
(iii) (p,0011,Z) \vdash (p,011,AZ) \vdash (p,11,AAZ) \vdash (q,11,AAZ)  \vdash (q,1,AZ) \vdash (q,\epsilon,Z)  \vdash (r,\epsilon,Z). Computação de aceitação: termina em um estado de aceitação e a cadeia de entrada é lida totalmente.

(b) Cadeia de entrada = 00111. Novamente, há várias computações, mas nenhuma delas é uma computação de aceitação.

(i) (p,00111,Z) \vdash (q,00111,Z) \vdash (r,00111,Z). O estado final é o de aceitação, mas a entrada não é aceita já que não foi lida.
(ii) (p,00111,Z) \vdash (p,0111,AZ) \vdash (q,0111,AZ). Não há mais estados possíveis.
(iii) (p,00111,Z) \vdash (p,0111,AZ) \vdash (p,111,AAZ) \vdash (q,111,AAZ)  \vdash (q,11,AZ) \vdash (q,1,Z)  \vdash (r,1,Z). O estado final é o de aceitação, mas a entrada não é aceita pois a cadeia não terminou de ser lida completamente.

AP e Linguagens livres de contexto[editar | editar código-fonte]

Toda gramática livre de contexto pode ser transformada em um autômato com pilha equivalente. O processo de derivação da gramática é simulada de uma forma mais à esquerda. Onde a gramática reescreve um não-terminal, o AP toma o não-terminal do topo da pilha pilha e substitui-la pelo lado direito de uma regra gramatical. Onde a gramática gera um símbolo terminal, o PDA lê um símbolo de entrada quando é o símbolo mais alto na pilha. De certa forma, a pilha do PDA contém os dados não transformados da gramática, correspondente a um percurso pré-ordem de uma árvore de derivação.

Tecnicamente, dada uma gramática livre de contexto, o AP é construído da seguinte forma:

  1. (1,\varepsilon,A,1,\alpha) para cada regra A\to\alpha (expand)
  2. (1,a,a,1,\varepsilon) para cada símbolo de terminal a (match)

Como resultado, obtemos um autômato com pilha de um único estado. O estado aqui é 1, aceitando a linguagem livre de contexto por pilha vazia. O símbolo inicial da pilha é igual ao axioma da gramática livre do contexto.

O inverso, encontrar uma gramática para um AP dado, não é tão simples. O truque é codificar dois estados do AP em símbolos não-terminais da gramática.

Teorema Para cada autômato com pilha M é possível construir uma gramática livre do contexto G tal que N(M)=L(G).

Autômato com Pilha Generalizado[editar | editar código-fonte]

Um Autômato com Pilha Generalizado APG é um AP que escreve uma cadeia inteira de um tamanho qualquer conhecido na pilha ou remove uma cadeia inteira da pilha em um único passo.

Um APG é formalmente definido como uma 6-upla:

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

onde Q, \Sigma\,, \Gamma\,, q0 e F são definidos da mesma forma que um AP.

\,\delta: Q \times  \Sigma_{\epsilon}  \times \Gamma^{*} \longrightarrow P( Q \times \Gamma^{*} )

é a função de transição.

Regras de computação para um APG são as mesmas que para AP, exceto que ai+1's e bi+1's são agora cadeias ao invés de símbolos.

APGs e APs são equivalentes, ou seja, se uma linguagem é reconhecida por um AP, ela também é reconhecida por um APG, e vice-versa.

Podemos formular uma prova analítica da equivalência entre APGs e APs usando a seguinte simulação:

Faça \delta(q1, w, x1x2...xm) \longrightarrow (q2, y1y2...yn) ser uma transição do APG

Onde q_1, q_2 \in Q, w \in\Sigma_{\epsilon}, x_1, x_2,\ldots,x_m\in\Gamma^{*}, m\geq0, y_1, y_2,\ldots,y_n\in\Gamma^{*}, n\geq 0.

Construa as seguintes transições para o AP:

\delta^{'}(q1, w, x1) \longrightarrow (p1, \epsilon)
\delta^{'}(p1, \epsilon, x2) \longrightarrow (p2, \epsilon)
\vdots
\delta^{'}(pm-1, \epsilon, xm) \longrightarrow (pm, \epsilon)
\delta^{'}(pm, \epsilon, \epsilon ) \longrightarrow (pm+1, yn)
\delta^{'}(pm+1, \epsilon, \epsilon ) \longrightarrow (pm+2, yn-1)
\vdots
\delta^{'}(pm+n-1, \epsilon, \epsilon ) \longrightarrow (q2, y1)

Softwares[editar | editar código-fonte]

  • Simulador de Autômatos- Software para criação, teste e conversão de Modelos Formais. Com interface gráfica.
  • SCTMF- Software para Criação e Teste de Modelos Formais.
  • JFlap- Software americano para testes com interface gráfica.
Teoria de autômatos: linguagem formal e gramática formal
Hierarquia
Chomsky
Gramática Linguagem Reconhecedor
Tipo-0 Irrestrita Recursivamente enumerável Máquina de Turing
-- -- Recursiva Máquina de Turing que sempre para
Tipo-1 Sensível ao contexto Sensível ao contexto Autômato linearmente limitado
Tipo-2 Livre de contexto Livre de contexto Autômato com pilha
Tipo-3 Regular Regular Autômato finito


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

  • Michael Sipser. Introdução à Teoria da Computação. Tradução brasileira de "Introduction to the Theory of Computation" (PWS Publishing Company, 2nd edition, 2005), por Ruy de Queiroz, revisão Newton Vieira, Cengarle Learning, 2007 ISBN 978-85-221-0499-4.
  • Jean-Michel Autebert, Jean Berstel, Luc Boasson, Context-Free Languages and Push-Down Automata, in: G. Rozenberg, A. Salomaa (eds.), Handbook of Formal Languages, Vol. 1, Springer-Verlag, 1997, 111-174.