flowchart LR
AF["Autômato finito<br/>memória: só o estado corrente"]
CT["Contador<br/>memória: um número natural"]
PD["Pilha<br/>memória: uma sequência<br/>acesso só pelo topo"]
DP["Duas pilhas<br/>poder de máquina de Turing"]
AF --> CT --> PD --> DP
AF -.-> R1["reconhece pouco<br/>decide tudo"]
PD -.-> R2["reconhece as linguagens<br/>livres de contexto<br/>ainda decide o essencial"]
DP -.-> R3["reconhece tudo<br/>quase nada é decidível"]
1 Módulo 09: Autômatos de Pilha — Resumo
Esta é a versão de revisão do módulo mais teórico do semestre; nenhuma demonstração aparece por inteiro, e para isso existem a versão completa do material e o livro. Use este texto para conferir se você reconstrói de cabeça a construção que parte da gramática — é ela que o próximo módulo transforma em código.
Se o autômato finito falha por ter pouca memória, por que não damos memória a ele e encerramos o assunto? A pergunta parece boba, e a resposta organiza o módulo inteiro: o que se quer não é mais memória, é a quantidade certa e a forma certa de acesso a ela.
1.1 Quanta memória dar à máquina
Já provamos que nenhum autômato finito reconhece parênteses balanceados, e a falha é estrutural: o estado é a única coisa que a máquina carrega adiante, então prefixos diferentes colidem no mesmo estado e passam a ser tratados como iguais. Falta ali uma contagem sem limite superior, consumida na ordem inversa da que foi produzida — o último parêntese aberto é o primeiro a fechar. A memória que resolve isso já está descrita nessa frase. No extremo oposto está a fita infinita de leitura e escrita livre, a máquina de Turing, sobre a qual quase nada é decidível; e um compilador precisa de garantias: que o analisador termina, que termina rápido, e que reconhece a linguagem documentada e não outra.
Entre os extremos há degraus. O contador resolve parênteses de um tipo só, mas não tipos diferentes aninhados: sabe que há três aberturas pendentes, não sabe quais. A pilha guarda a sequência, e é o degrau que interessa. Logo acima está o abismo — uma máquina finita com duas pilhas já equivale a uma de Turing.
Pare e pense. Se a segunda pilha custa a decidibilidade inteira, o que exatamente a primeira compra? Guarde a resposta: ela é o resumo honesto de tudo o que vem a seguir.
1.2 A máquina, com rigor
Um autômato de pilha é a sétupla M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F) — estados, alfabeto de entrada, alfabeto de pilha, transição, estado inicial, símbolo inicial de pilha e finais. Tudo mora na assinatura da transição:
\delta : Q \times (\Sigma \cup \{\varepsilon\}) \times \Gamma \longrightarrow \mathcal{P}_{\text{fin}}(Q \times \Gamma^{*}).
flowchart TB
ENT["Entrada<br/>lida da esquerda para a direita,<br/>sem retorno, ou não lida<br/>quando a transição é vazia"]
TOPO["Topo da pilha<br/>único símbolo visível"]
CTRL["Controle finito<br/>estado corrente"]
ACAO["Transição escolhida<br/>troca o topo por uma cadeia de símbolos<br/>e muda de estado"]
PILHA["Pilha<br/>altura ilimitada<br/>o resto do conteúdo é invisível"]
ENT --> CTRL
TOPO --> CTRL
CTRL --> ACAO
ACAO --> PILHA
PILHA --> TOPO
Leia devagar. A segunda componente inclui a cadeia vazia, então há transições que não consomem símbolo algum, e a construção central do módulo é feita quase toda delas. A terceira exige sempre um símbolo de pilha: toda transição consulta o topo, logo pilha vazia significa máquina travada. O contradomínio é um conjunto de pares, e é aí que mora o não determinismo. A cadeia de cada par substitui o topo: vazia, o topo some; com um símbolo, é trocado; com vários, a pilha cresce.
A convenção que produz o erro mais comum do módulo. O símbolo mais à esquerda da cadeia substituta fica no topo. Quem empilha o conteúdo dela na ordem em que está escrito obtém a ordem invertida e passa a reconhecer as cadeias espelhadas — e o defeito é invisível quando a cadeia tem zero ou um símbolo, que é justamente o caso dos primeiros exemplos que qualquer um testa. Trate a substituição como troca de bloco, nunca como sequência de empilhamentos.
Para falar da computação sem ambiguidade usa-se a descrição instantânea, a tripla com estado corrente, entrada ainda não lida e pilha escrita do topo para a base: um passo é (q, aw, X\beta) \vdash (p, w, \gamma\beta), e a notação já registra que a porção \beta abaixo do topo atravessa o passo intocada.
Um exemplo pequeno fixa tudo. Para as cadeias com tantos a quantos b, nessa ordem, bastam três estados: cada a empilha uma marca, o primeiro b muda de estado e desempilha, e quando o símbolo de fundo reaparece uma transição vazia leva ao final. Três estados e uma pilha resolvem o que nenhum autômato finito resolve com nenhuma quantidade de estados.
1.3 Duas maneiras de dizer sim
A cadeia é aceita quando a máquina consome a entrada inteira e chega a um estado de F; o conteúdo final da pilha é irrelevante. É a convenção mais próxima do autômato finito e a padrão para máquinas determinísticas.
A cadeia é aceita quando a máquina consome a entrada inteira e a pilha fica vazia, esteja ela no estado que estiver; o conjunto de finais costuma ser tomado vazio. É a convenção mais cômoda quando o autômato nasce de uma gramática.
Nas duas a condição é existencial: basta que alguma sequência de escolhas chegue à aceitação. E as duas reconhecem a mesma classe, por construções que dependem do mesmo truque — um símbolo novo no fundo da pilha, fora do alfabeto original —, sem o qual a máquina simplesmente trava ao esvaziar e não sinaliza nada. Daí um fato prático: na aceitação por pilha vazia, se a pilha passa pelo vazio num instante intermediário, o prefixo lido até ali também é aceito. É a razão teórica de todo analisador real exigir um marcador de fim de entrada — sem ele, quem esvazia a pilha ao completar a primeira declaração reporta “programa válido” e ignora o resto do arquivo.
1.4 Da gramática ao autômato
Este é o coração do módulo: quem o entende chega ao analisador descendente reconhecendo o que implementa. Dada uma gramática livre de contexto, construo um autômato com um único estado, aceitação por pilha vazia, alfabeto de pilha igual à união de variáveis e terminais, e símbolo inicial de pilha igual ao da gramática. A transição tem duas famílias, só isso. Expansão: com uma variável no topo, troque-a pelo corpo de alguma produção dela, sem consumir entrada. Casamento: com um terminal no topo, remova-o exigindo o mesmo terminal na entrada.
flowchart TB
INI["Pilha começa com o símbolo<br/>inicial da gramática"]
DEC{"O que está no topo?"}
EXP["Expande<br/>troca a variável pelo corpo<br/>de uma de suas produções<br/>sem consumir entrada"]
CASA["Casa<br/>remove o terminal do topo<br/>e consome o mesmo símbolo da entrada"]
FIM["Pilha vazia:<br/>aceita se a entrada também acabou"]
INI --> DEC
DEC -->|"uma variável"| EXP
DEC -->|"um terminal"| CASA
EXP --> DEC
CASA --> DEC
DEC -->|"nada"| FIM
Um estado só merece pausa: todo o poder está na pilha e nenhum no controle finito. O invariante que vale memorizar é este — se u é o prefixo já consumido e \alpha é a pilha lida do topo para a base, a gramática deriva u\alpha por uma derivação mais à esquerda. Em português: a pilha é uma lista de obrigações, a parte da forma sentencial que ainda não foi casada com a entrada. Expandir troca uma obrigação por obrigações menores; casar cumpre uma elementar; aceitar é não sobrar obrigação nem entrada.
Trace sobre a gramática de expressões com precedência estratificada e duas coisas aparecem. Os primeiros passos não consomem nada — a máquina reorganiza a pilha antes de ler o primeiro símbolo, assinatura da estratégia descendente, em que a decisão vem antes da evidência que a justificaria. E o resultado que dá sentido a tudo: a sequência de produções das expansões de uma computação que aceita é exatamente uma derivação mais à esquerda — não é analogia, é o mesmo objeto.
A armadilha do traçado desonesto. Traçando à mão é quase irresistível espiar a entrada para decidir qual produção expandir; o traçado sai certo e esconde justamente o que deveria mostrar. Em cada expansão com mais de uma produção possível, anote que houve escolha e qual informação a dispensaria — é a anotação, e não o traçado, que ensina.
Onde cada adivinhação se resolve é onde nasce o próximo módulo. Algumas cedem a um símbolo de antecipação, quando os corpos começam por símbolos diferentes; a da recursão à esquerda não cede a nenhuma, porque a expansão recoloca a mesma variável no topo sem consumir nada. No modelo isso não incomoda, já que ele quantifica em vez de executar; numa implementação determinística, uma função que chama a si mesma antes de consumir símbolo não retorna nunca.
A volta completa a equivalência. Como a gramática não tem noção de estado, cada variável codifica um trecho de computação — uma tripla de estado de partida, símbolo de pilha e estado de chegada — e, como os estados intermediários são desconhecidos, a gramática gera todas as combinações e explode. Ninguém a usa para produzir gramáticas; ela existe para demonstrar o teorema central: uma linguagem é gerada por alguma gramática livre de contexto se e somente se é aceita por algum autômato de pilha, resultado do início dos anos 1960, em trabalhos independentes de Noam Chomsky, de 1962, de Robert Evey e de Marcel-Paul Schützenberger. A lição é que estado e pilha não são recursos independentes: num analisador recursivo o estado está todo na pilha de chamadas.
1.5 Determinismo, e o que ele custa
Aqui vem o resultado que contraria a intuição formada na determinização. Um autômato de pilha é determinístico quando, para cada estado e cada topo, há no máximo uma continuação por símbolo de entrada e a existência de uma transição vazia exclui todas as que leem símbolo ali — essa segunda cláusula passa despercebida, e sem ela a máquina escolheria entre agir por conta própria e ler a entrada, que é não determinismo disfarçado.
flowchart TB
subgraph REG["Nível regular"]
AFN["Autômato finito<br/>não determinístico"]
AFD["Autômato finito<br/>determinístico"]
AFN -->|"construção de subconjuntos<br/>preço: explosão de estados"| AFD
end
subgraph LLC["Nível livre de contexto"]
APN["Autômato de pilha<br/>não determinístico"]
APD["Autômato de pilha<br/>determinístico"]
APN -.->|"não existe construção geral:<br/>um ramo carrega uma pilha,<br/>e conjuntos de pilhas não cabem<br/>em estrutura finita"| APD
end
REG --> LLC
A classe determinística está estritamente contida nas linguagens livres de contexto, e o exemplo canônico são os palíndromos de comprimento par: quem empilha a primeira metade e casa a segunda contra o topo precisaria decidir, a cada símbolo, onde fica o meio — decidir cedo o que só se sabe tarde. E o método do nível regular não sobe de andar: a construção de subconjuntos funcionava porque subconjuntos de um conjunto finito ainda são finitos, enquanto aqui um ramo é um estado e uma pilha, objeto ilimitado. É essa fronteira que explica por que a análise léxica se resolve com um algoritmo único e a sintática não.
| Aspecto | Nível regular | Nível livre de contexto |
|---|---|---|
| Modelo reconhecedor | autômato finito | autômato de pilha |
| Determinismo e não determinismo | equivalentes | não equivalentes |
| Conversão do não determinístico | construção de subconjuntos | não existe em geral |
| Fechamento sob complemento | classe inteira | só a subclasse determinística |
| Custo do reconhecimento | linear | linear só nas subclasses determinísticas |
A tradução para a engenharia é severa: o algoritmo geral que trata qualquer gramática livre de contexto reconhece uma cadeia de comprimento n em tempo proporcional a n^{3}, e tempo linear exige determinismo. Daí a decisão que você herda — a análise sintática real vive em subclasses determinísticas, e a escolha da gramática vira parte do projeto do compilador. Não é só perda: a subclasse determinística é fechada sob complemento, o que sustenta a detecção de erro em posição precisa, coisa que um reconhecedor não determinístico não sabe reportar. E a equivalência entre dois determinísticos é decidível, resultado difícil de Géraud Sénizergues reconhecido com o Prêmio Gödel em 2002, enquanto a mesma pergunta sobre gramáticas quaisquer é indecidível.
1.6 Os limites da classe
O lema do bombeamento reaparece com uma diferença estrutural: a decomposição é em cinco partes, z = uvwxy, e duas são bombeadas juntas, na mesma quantidade, dentro de uma janela limitada e sem que ambas sejam vazias.
flowchart TB
LONGA["Cadeia longa na linguagem"]
ALTA["Árvore de derivação alta:<br/>algum caminho da raiz até uma folha<br/>repete uma mesma variável"]
DEC["Decomposição em cinco partes:<br/>u, v, w, x, y"]
BOMBA["A variável repetida permite repetir ou apagar<br/>o trecho intermediário: v e x crescem juntos"]
JANELA["Restrição decisiva:<br/>o trecho central cabe numa janela<br/>de tamanho limitado pela gramática"]
LONGA --> ALTA --> DEC --> BOMBA
DEC --> JANELA
A intuição vem da árvore, não da máquina: em forma normal de Chomsky cada nó interno tem no máximo dois filhos, então muitas folhas obrigam a árvore a ser alta, e num caminho alto alguma variável se repete pelo princípio das casas dos pombos. As duas versões do lema estão no mesmo trabalho de Yehoshua Bar-Hillel, Micha Perles e Eliahu Shamir, de 1961. Na linguagem de três blocos com contagens iguais, a janela limitada garante que as partes bombeadas tocam no máximo dois blocos; bombeando uma vez, um cresce e outro fica parado. Escolha cadeias em que as partes que precisam corresponder fiquem o mais distantes possível, e lembre: o lema é condição necessária, não suficiente.
A frase que resume tudo. Uma pilha conta uma coisa de cada vez. Ela conta um bloco e desconta com o seguinte, mas ao fim da verificação a quantidade foi consumida e não há de onde tirá-la de novo — consultar uma pilha em profundidade exige destruí-la.
O fechamento reserva a segunda surpresa: união, concatenação, fecho e reverso continuam valendo, mas interseção e complemento não — e a interseção com uma linguagem regular, sim, porque o autômato finito do produto não traz uma segunda pilha. A decidibilidade também encolhe: seguem decidíveis a pertinência, a vacuidade e a finitude, e tornam-se indecidíveis a equivalência de duas gramáticas e a ambiguidade de uma. Não existe, nem pode existir, ferramenta que responda com certeza se uma gramática é ambígua; as reais verificam se ela pertence a uma subclasse e reportam conflitos quando não pertence — e conflito não é sinônimo de ambiguidade, confusão que custa horas procurando um defeito que não existe.
flowchart TB
T3["Tipo 3 — regulares<br/>autômato finito<br/>análise léxica, custo linear"]
T2["Tipo 2 — livres de contexto<br/>autômato de pilha<br/>análise sintática, só nas subclasses determinísticas"]
T1["Tipo 1 — sensíveis ao contexto<br/>autômato linearmente limitado<br/>formalismo recusado por custo na análise semântica"]
T0["Tipo 0 — irrestritas<br/>máquina de Turing<br/>fronteira do decidível"]
T3 --> T2 --> T1 --> T0
T0 -.-> LIM["Daqui vêm os limites de qualquer fase:<br/>perguntas sobre o comportamento do programa<br/>são indecidíveis em geral"]
Com dois andares cobertos, a leitura vertical é o que interessa: a restrição sobre a forma das produções determina ao mesmo tempo a classe alcançada e a máquina necessária, e afrouxá-la faz a classe crescer, o custo subir e o conjunto de perguntas decidíveis encolher. A análise léxica vive no tipo 3; a sintática, nas subclasses determinísticas do tipo 2; a semântica seria de tipo 1 e a prática a abandona de olhos abertos, verificando por código ou por gramáticas de atributos; e o tipo 0 delimita o que nenhuma fase pode fazer.
1.7 Síntese
Volto à pergunta da abertura: a primeira pilha compra as correspondências aninhadas com contagem sem limite, sem entregar a decidibilidade que a segunda destruiria de uma vez — é a restrição de acesso, e não a capacidade, que faz o modelo valer a pena. O núcleo do módulo é a equivalência entre gramáticas livres de contexto e autômatos de pilha, sobretudo a construção que parte da gramática, e a identidade entre expansões e derivação mais à esquerda, que faz o analisador descendente parecer natural em vez de mágico. No projeto do seu grupo a entrega é o traçado à mão sobre a gramática que vocês escreveram, com a pilha orientada e cada escolha anotada — faça isso antes do próximo módulo, porque quem traçou reconhece o algoritmo que vai implementar, e quem pulou acha que ele surgiu do nada.