Autômatos a Pilha
Autômatos a 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.
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, isto é, elas não possuem uma pilha. Autômatos de 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 a 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 de Pilha pode ignorar a pilha e deixá-la como está. A escolha pela manipulação ou pela não manipulação da mesma é determinada pela relação de transição.
Autômatos de Pilha são equivalentes a gramáticas livres de contexto, isto é, para toda gramática livre de contexto existe um Autômato de Pilha que reconhece a mesma linguagem, e vice versa.
Se permitíssemos que um Autômato Finito tivesse acesso à duas pilhas ao invés de apenas uma, obtemos um dispositivo ainda mais poderoso, com poder equivalente ao de uma Máquina de Turing.