1. Por que precisamos de uma pilha?
Um Autômato Finito (AFD/AFN) possui uma memória estritamente finita, representada exclusivamente pelos seus estados. Ele consegue lembrar "onde está", mas não consegue contar quantidades arbitrariamente grandes.
as seguidos de bs (como ab, aabb, aaabbb, etc.), a máquina precisa guardar quantos as foram lidos para depois conferir se há exatamente o mesmo número de bs. Como n pode ser qualquer número (10, 100, 10.000...), um autômato finito precisaria de infinitos estados, o que viola sua definição!
A solução é equipar a máquina com uma memória auxiliar simples e organizada: uma Pilha (LIFO — Last-In, First-Out).
2. A Definição Formal (A 7-Tupla)
Formalmente, um Autômato com Pilha é definido como:
Conjunto finito de estados de controle (ex: {q0, q1, q2}).
Símbolos que formam as palavras lidas da fita (ex: {a, b}).
Símbolos que podem ser armazenados na memória pilha (ex: {A, Z0}).
O estado onde a máquina se encontra antes de ler o primeiro caractere (q₀ ∈ Q).
Símbolo inicialmente presente no fundo da pilha (Z₀ ∈ Γ). Evita desempilhar além do fundo.
Conjunto de estados de aceitação (F ⊆ Q).
3. Como Funcionam as Transições (δ)
No modelo adotado neste simulador e na literatura clássica (Sipser, Hopcroft/Ullman, Paulo Blauth Menezes), cada transição possui o formato:
ε para não consumir fita).
ε para não desempilhar).
ε se apenas desempilhou).
| Notação | O que significa na prática? |
|---|---|
| a, Z0 ➔ AZ0 | Lê 'a', confere se o topo é 'Z0' e empilha 'A' por cima de 'Z0' (o novo topo passa a ser 'A'). |
| b, A ➔ ε | Lê 'b', desempilha 'A' do topo e não empilha nada novo (POP puro). |
| ε, Z0 ➔ Z0 | Transição espontânea (sem ler da fita), apenas verifica se voltou à base 'Z0'. |
4. Critérios de Aceitação
Na Teoria da Computação, existem duas formas equivalentes de aceitação para autômatos com pilha:
A palavra é aceita se, após ler toda a fita de entrada, o autômato atinge um estado final q ∈ F. A pilha pode terminar com qualquer conteúdo.
A palavra é aceita se, após ler toda a fita de entrada, a pilha é completamente esvaziada (conteúdo = vazio). O estado onde a máquina parou não precisa ser final.
Muito comum em exercícios didáticos: exige simultaneamente atingir um estado de aceitação q ∈ F e deixar a pilha limpa.
5. Guia Rápido de Interação
PUSH em verde e POP em amarelo).
- Tabela de δ em destaque: durante a simulação, a linha da regra aplicada no passo atual fica marcada na tabela.
- Salvamento automático: ao reabrir a página, o último autômato volta como você deixou. Os Exemplos recomeçam do zero.
- Exportações: o PNG sai sempre com fundo branco, e o botão LaTeX também baixa um
.texcompleto e compilável.