Autômato com pilha

Autômato com pilha

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
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.

Definição formal
Um 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