Autômato de Pilha

Autômato de Pilha
Analogamente às Linguagens Regulares, a Classe das Linguagens Livres do Contexto pode ser associada a um formalismo do tipo autômato, denominado Autômato com Pilha.
O Autômato com Pilha é análogo ao Autômato Finito que reconhece as Linguagens Livre de
Contexto, basicamente um AFNDε incluindo uma pilha como memória auxiliar e a facilidade de nãodeterminismo. A pilha é independente da fita de entrada e não possui limite máximo de tamanho
("infinita").
Estruturalmente, sua principal característica é que o último símbolo gravado é o primeiro a ser lido.
(FIFO last in first out ). Ao contrário da fita de entrada, a pilha pode ser lida e alterada durante um processamento; A base de uma pilha é fixa e define o seu início.
O topo é variável e define a posição do último símbolo gravado.
A facilidade de não-determinismo é importante e necessária, pois aumenta o poder computacional dos Autômatos com Pilha, permitindo reconhecer exatamente a Classe das Linguagens
Livres do Contexto e Gramatica Livres de Contexto. Por exemplo, o reconhecimento da linguagem:

{ wwr | w é palavra sobre { a, b } } só é possível por um Autômato com Pilha Não-Determinístico.

Caracteristicas da Transicao
Um AFP em uma transição:
• Consome da entrada o símbolo que ele utiliza na transição, com exceção de λ .
• Substitui o símbolo do topo da pilha por qualquer cadeia. o Se for λ , corresponde a uma extração da pilha. o Se for o mesmo símbolo que estava presente no topo da pilha, a pilha não se altera. o Podemos colocar uma cadeia, então o topo é substituído pela cadeia.
•

Normalmente usa-se para símbolo inicial da pilha o carácter especial # (cardinal).
Teoria da Computação
Prof. Gláucya Carreiro Boechat

1

Definicao
P = (Q, Σ, Γ, δ, q0, Z0, F)
Q: conjunto finito de estados
Σ: alfabeto (simbolos de entrada)
Γ: alfabeto finito a pilha δ: função de transição - δ: Q x (Σ ∪ λ } ) x Γ→Q x Γ* q0 : estado inicial
Z0: símbolo de início da pilha