CCT-UFCA/Ciência da Computação/Autômatos e Linguagens Formais/Autômatos com Pilha

Autômatos com Pilha (AP) são AFNs com a adição de uma pilha ilimitada, onde durante a leitura a máquina pode empilhar e desempilhar símbolos. Seja a, b e c símbolos e q₁ e q₂ estados de um AP. Quando temos uma transição "a, b → c" indo de q₁ para q₂, significa que caso ele esteja lendo o símbolo a, ele vai desempilhar b da pilha, empilhar c e vai para q₂. Caso queira fazer o AP ler um símbolo e ignorar a pilha, basta fazer uma transição da forma "a, ε → ε".

Uma boa forma de entender o funcionamento dos APs é reconhecer a linguagem {0ⁿ1ⁿ | n ≥ 0}. A ideia é utilizar a pilha para armazenar a quantidade total de 0s lidos e em seguida desempilhar os 0s da pilha para cada 1 lido. Com isso, caso a pilha esteja vazia depois de ler toda a cadeia de entrada, a entrada será aceita. O problema é saber quando que a pilha estará vazia. Para isso, podemos iniciar o AP com a transição "ε, ε → $". Logo, caso a cadeia esteja na linguagem, na pilha restará apenas o símbolo $. Verificamos com a transição "ε, $ → ε" se a pilha está vazia depois do empilhamento e desempilhamento dos 0s, caso seja verdade, então a cadeia será aceita.

Definição Formal

Um autômato com pilha (AP) é uma 6-upla (Q, Σ, Γ, δ, q₀, F) em que:

1. Q é um conjunto finito de estados;
2. Σ é o alfabeto de entrada;
3. Γ é o alfabeto da pilha;
4. δ: Q x (Σ ∪ {ε}) x (Σ ∪ {ε}) → P(Q x (Γ ∪ {ε})) é a função de transição;
5. q0 ∈ Q é o estado inicial;
6. F ⊆ Q é o conjunto dos estados finais.