DC-UFRPE/Licenciatura Plena em Computação/Teoria da Computação/Autômatos de pilha (AP)
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
editarAutômatos com pilha diferem da definição normal de máquinas de estados finitos de duas maneiras:
- Eles podem fazer uso da informação que está no topo da pilha para decidir qual transição deve ser efetuada;
- 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.Predefinição:Carece de fontes
Definição formal
editarUm autômato de pilha é formalmente definido por uma 6-tupla:
Onde:
- é um conjunto finito de estados.
- é um conjunto finito de símbolos, denominado alfabeto de entrada.
- é um conjunto finito de símbolos, denominado alfabeto da pilha.
- é a relação de transição.
- é o estado inicial.
- é 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
editarA fim de formalizar a descrição semântica dos autômatos com pilha, introduziremos uma descrição da situação atual. Qualquer 3-upla é chamada de uma descrição instantânea (ID) de , que inclui o estado atual, a parte 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 define a relação origina de na descrição instantânea (ID). Para instruções existe um passo , para todo e todo .
Em geral, autômatos com pilha são não determinísticos, o que significa dizer que dada uma descrição instantânea pode 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 com o símbolo inicial da pilha na pilha e uma cadeia na fita de entrada e, portanto, com a descrição inicial . 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 ), quanto por pilha vazia ( ), 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:
- com e (Estado final)
- com (Pilha vazia)
Aqui representa os fechos reflexivos e transitivos da relação origina 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 é possível construir um outro autômato com pilha tal que , e vice versa, para cada autômato com pilha é possível construir um autômato com pilha tal que
Exemplo
editarA seguir é a descrição formal do AP, que reconhece a linguagem por estado final:
, onde
consiste nas seis instruções seguintes:
, , , , , e .
Ou seja, no estado para cada símbolo que for lido, um é colocado na pilha. Empilhar um símbolo no topo de um outro é formalizado como trocar o símbolo por . No estado , para cada símbolo lido, um a é desempilhado. Em um outro momento, o autômato se move do estado para o estado , enquanto ele pode mover do estado para o estado de aceitação somente quando a pilha possuir um único .
Representamos a instrução como uma ponte que sai do estado para o estado rotulada por (leia ; substitui por ).
Entendendo o processo de computação
editarA 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 para o estado . Apenas uma dessas computações aceita.
- (i) . O estado final é o de aceitação, mas a entrada não é aceita pois a cadeia não terminou de ser lida completamente.
- (ii) . Não há mais estados possíveis..
- (iii) . 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) . O estado final é o de aceitação, mas a entrada não é aceita já que não foi lida.
- (ii) . Não há mais estados possíveis.
- (iii) . 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
editarToda 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:
- para cada regra (expand)
- para cada símbolo de terminal (match)
Como resultado, obtemos um autômato com pilha de um único estado. O estado aqui é , 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 é possível construir uma gramática livre do contexto tal que .
Autômato com Pilha Generalizado
editarUm 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:
onde Q, , , q0 e F são definidos da mesma forma que um AP.
- :
é 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 (q1, w, x1x2...xm) (q2, y1y2...yn) ser uma transição do APG
Onde , , , , , .
Construa as seguintes transições para o AP:
- (q1, w, x1) (p1, )
- (p1, , x2) (p2, )
- (pm-1, , xm) (pm, )
- (pm, , ) (pm+1, yn)
- (pm+1, , ) (pm+2, yn-1)
- (pm+n-1, , ) (q2, y1)
Softwares
editarReferências
editar- 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.