# Autómatos de pilha

PDA com um exemplo completo para 0n1n e a equivalência com gramáticas.

Página: https://resumos.rgo.pt/cadeiras/tc/automatos-pilha/

Um **autómato de pilha** (PDA, de _pushdown automaton_) é um NFA com uma pilha: a cada passo, além de ler (ou não) um símbolo, pode empilhar ou desempilhar símbolos. A pilha é memória ilimitada mas só com acesso ao topo, e é exatamente o que faltava para reconhecer $\{0^n 1^n\}$. Esta página constrói esse autómato e enuncia a equivalência com gramáticas livres de contexto.

## O modelo

Um PDA tem estados finitos, alfabeto de entrada $\Sigma$ e alfabeto de pilha $\Gamma$ (que pode incluir um marcador de fundo como undefined\\varepsilon$ se não lê), símbolo no topo da pilha, estado destino e o que empilhar (ou desempilhar). Aceita por **estado final** (terminar num estado de aceitação após ler tudo, com qualquer conteúdo na pilha) ou por **pilha vazia**; os dois critérios são equivalentes.

Em notação compacta (à Sipser), a transição que troca de fase escreve-se $\delta(q_0, 1, 0) = \{(q_1, \varepsilon)\}$: lê-se “no estado $q_0$, ao ler $1$ com $0$ no topo, vai para $q_1$ e empilha $\varepsilon$”, ou seja, desempilha sem pôr nada no lugar. O triplo antes da seta é a condição, o par depois é o efeito.

A intuição: a parte finita (estados) trata o que os DFA já tratavam, e a pilha guarda contagens e chamadas por fechar. É o mesmo salto dos parênteses bem formados: empilha ao abrir, desempilha ao fechar.

## Exemplo resolvido: PDA para $\{0^n 1^n\}$

Linguagem sobre $\{0, 1\}$: $n$ zeros seguidos de $n$ uns, incluindo $\varepsilon$ ($n = 0$). Estratégia: empilha um marcador por cada $0$ lido, depois desempilha um por cada $1$. Aceita se a pilha esvaziar exatamente no fim.

Estados: $q_0$ (inicial, a ler zeros), $q_1$ (a ler uns), $q_f$ (aceitação). Alfabeto de pilha: \\{0, \\}$, com $$$ no fundo.

```
Inicialização:
  q0 --(ε, topo nada: empilha $)--> q0     (põe o marcador de fundo)
Leitura de zeros (fica em q0):
  q0 --(0, topo x: empilha 0 por cima)--> q0   para qualquer x
Transição para os uns:
  q0 --(1, topo 0: desempilha)--> q1
Aceitação (inclui a palavra vazia, com n = 0):
  q0 --(ε, topo $: desempilha)--> qf
Leitura de uns (fica em q1):
  q1 --(1, topo 0: desempilha)--> q1
Aceitação (cont.):
  q1 --(ε, topo $: desempilha)--> qf
```

Corre $w = 0011$: empilha \\$$, empilha 0$, empilha $0$(pilha:$0,0,$$do topo para o fundo). Lê$1$: desempilha um $0$, vai para $q\_1$. Lê $1$: desempilha o outro $0$(pilha:$$$). Fim da palavra em $q\_1$com topo$$$: transição $\\varepsilon$para$q\_f$. Aceite.

![PDA com três estados. O estado q0 tem um ciclo que empilha 0, vai para q1 ao ler 1 com 0 no topo e vai para qf sem ler com o marcador no topo. O estado q1 tem um ciclo que desempilha com 1 e vai para qf sem ler com o marcador no topo. O estado qf, de aceitação, não tem saídas.](https://resumos.rgo.pt/cadeiras/tc/automatos-pilha/figura-1.svg)

Os rótulos dizem “símbolo lido, topo exigido: efeito na pilha”, com `e` no lugar do $\varepsilon$ para o Graphviz desenhar. O traço completo para $0011$, com a pilha do topo para o fundo:

| Estado | Por ler | Pilha |
| --- | --- | --- |
| $q_0$ | `0011` | `$` |
| $q_0$ | `011` | `0, $` |
| $q_0$ | `11` | `0, 0, $` |
| $q_1$ | `1` | `0, $` |
| $q_1$ | (vazia) | `$` |
| $q_f$ | (vazia) | (vazia) |

![Quatro instantâneos da pilha ao correr 0011: só o marcador, depois com dois zeros por cima, depois com um zero após o primeiro um, e por fim só o marcador após o segundo um.](https://resumos.rgo.pt/cadeiras/tc/automatos-pilha/figura-2.svg)

A mesma receita em código, com a pilha trocada por uma contagem (a altura da pilha é o número de zeros por emparelhar):

```python
def pda(w):
    if w == "":
        return True
    zeros = 0
    while zeros < len(w) and w[zeros] == "0":
        zeros += 1
    uns = w[zeros:]
    return zeros > 0 and len(uns) == zeros and all(s == "1" for s in uns)

for w in ["0011", "010", ""]:
    print(w or "epsilon", "aceite" if pda(w) else "rejeitada")
```

E porque é que $010$ é rejeitada? Lê $0$ (empilha), lê $1$ (desempilha, vai para $q_1$ com pilha \\$$), lê 0$: não há transição de $q\_1$a ler$0$. O caminho morre, e não há outro. Rejeitada, como devia.

Receita para contar com a pilha

Para “tantos $a$ como $b$”: empilha nos $a$, desempilha nos $b$, com um marcador de fundo para detetar o zero. Para “mais $a$ que $b$”: igual, mas aceita com pilha não vazia. Quase todos os exercícios de PDA são variantes desta receita com dois estados de fase.

## PDA equivale a CFG

**Teorema.** Uma linguagem é reconhecida por algum PDA se e só se é gerada por alguma CFG. As linguagens desta família chamam-se **livres de contexto**.

A prova tem dois sentidos, e cada um é uma construção:

*   De CFG para PDA: o autómato simula derivações mais à esquerda, mantendo a forma sentencial na pilha e expandindo variáveis no topo. Se a palavra esvaziar a pilha, aceita.
*   De PDA para CFG: a gramática ganha uma variável $[pAq]$ para cada par de estados $(p, q)$ e símbolo $A$, significando “de $p$ com $A$ no topo até $q$ com $A$ removido”. As regras copiam as transições do autómato.

Não decores as construções símbolo a símbolo; fixa o que elas implicam: tudo o que provaste para gramáticas (como a árvore sintática) vale para autómatos de pilha, e vice-versa. Em particular, há um lema da repetição para linguagens livres de contexto (com duas partes repetíveis), que exclui linguagens como $\{0^n 1^n 2^n\}$. O padrão é o mesmo da página sobre [limites das linguagens regulares](https://resumos.rgo.pt/cadeiras/tc/automatos-pilha/limites-regulares/): conta finita contra crescimento ilimitado.

## Para levar para a próxima página

A pilha resolve a contagem, mas há linguagens que nem ela alcança, como $\{0^n 1^n 2^n\}$, e há perguntas que nenhuma máquina responde. O modelo sem restrições é a [máquina de Turing](https://resumos.rgo.pt/cadeiras/tc/automatos-pilha/turing-decidibilidade/).