Autómatos de pilha

Para reconhecer $a^nb^n$, guarda um marcador por cada $a$ e retira um por cada $b$. Os estados controlam a ordem dos blocos. A pilha guarda os marcadores, com o último a entrar no topo e a ser o primeiro a sair.

Um autómato de pilha, PDA, combina essa memória com escolhas não determinísticas. Vamos seguir $aabb$ e relacionar a computação com a gramática $S\to aSb\mid\varepsilon$.

O modelo

Um autómato de pilha, PDA, é $P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$. Além dos componentes finitos habituais, $\Gamma$ é o alfabeto da pilha e $Z_0\in\Gamma$ é o símbolo que está inicialmente nela.

A função de transição recebe estado, letra de entrada ou $\varepsilon$, e símbolo do topo:

$$\delta:Q\times(\Sigma\cup\{\varepsilon\})\times\Gamma \to\mathcal P_{\mathrm{fin}}(Q\times\Gamma^*).$$

O resultado é um conjunto finito de escolhas. O par $(p,\gamma)$ significa ir para $p$ e substituir o topo por $\gamma$. Escreve a pilha com o topo à esquerda. Se o topo $X$ é substituído por $YZ$, fica $Y$ por cima de $Z$. Se $\gamma=\varepsilon$, retiras o topo; se $\gamma=X$, a pilha não muda.

No diagrama, $a,X/\gamma$ representa essa operação. A letra $a=\varepsilon$ não consome entrada, mas a operação ainda exige que $X$ esteja no topo.

Configurações e aceitação

Uma configuração, ou descrição instantânea, é $(q,w,\gamma)$: estado atual, entrada ainda por ler e pilha atual. Se $(p,\alpha)\in\delta(q,a,X)$, então

$$(q,aw,X\beta)\vdash(p,w,\alpha\beta).$$

O que está abaixo do topo não interfere na escolha da transição, e $\vdash^*$ representa zero ou mais passos.

Na aceitação por estado final, exige $(q_0,w,Z_0)\vdash^*(f,\varepsilon,\gamma)$ para algum $f\in F$. A pilha pode conservar símbolos. Na aceitação por pilha vazia, exige $(q_0,w,Z_0)\vdash^*(q,\varepsilon,\varepsilon)$, sem condição sobre $q$.

Em ambos os casos, a entrada tem de estar consumida. Estar num final ou ter a pilha vazia enquanto restam letras não aceita a palavra.

Exemplo resolvido: PDA para aⁿbⁿ

Reconhece $\{a^nb^n\mid n\ge0\}$ por estado final. Usa $q_0$ para ler $a$, $q_1$ para ler $b$ e $q_f$ como final. A pilha começa em $Z$ e guarda marcadores $A$.

Origem	Entrada	Topo	Destino	Substituição
$q_0$	$a$	$Z$	$q_0$	$AZ$
$q_0$	$a$	$A$	$q_0$	$AA$
$q_0$	$b$	$A$	$q_1$	$\varepsilon$
$q_1$	$b$	$A$	$q_1$	$\varepsilon$
$q_0$	$\varepsilon$	$Z$	$q_f$	$Z$
$q_1$	$\varepsilon$	$Z$	$q_f$	$Z$

As restantes transições não existem; em particular, $q_f$ não tem saídas. O estado $q_0$ pode aceitar $\varepsilon$ pela transição vazia, mas essa transição não aceita quando resta entrada por consumir.

A computação que aceita $aabb$ é:

$$\begin{aligned} (q_0,aabb,Z)&\vdash(q_0,abb,AZ)\\ &\vdash(q_0,bb,AAZ)\\ &\vdash(q_1,b,AZ)\\ &\vdash(q_1,\varepsilon,Z)\\ &\vdash(q_f,\varepsilon,Z). \end{aligned}$$

Em $aab$, sobra um $A$ quando a entrada acaba, e não há transição para o final. Em $abb$, o segundo $b$ encontra $Z$ e o ramo bloqueia. Em $aba$, o estado $q_1$ não tem transição para $a$, impedindo o regresso ao primeiro bloco.

O invariante é: em $q_0$ há um $A$ por cada $a$ lido; em $q_1$ há um $A$ por cada $a$ ainda não emparelhado com um $b$. Só chegas ao final com zero marcadores e entrada consumida.

Segue $aabb$ por passos e compara com $aab$ ou $aba$. A fronteira conserva as configurações de todos os ramos, incluindo os que escolhem uma transição vazia antes de a entrada acabar. O percurso aceitante mostra as substituições da pilha.

MáquinaPDA: aⁿbⁿPDA: palíndromos paresCriar PDA

Editar estados e transições

Declara os estados, os alfabetos da entrada e da pilha, o início e os finais. Cada transição tem a forma origem entrada topo -> destino substituição. ε na entrada não lê uma letra; ε na substituição retira o topo. Não há transições com a pilha vazia.

estados q0 q1 qf alfabeto a b pilha Z A inicial q0 Z finais qf q0 a Z -> q0 AZ q0 a A -> q0 AA q0 b A -> q1 ε q1 b A -> q1 ε q0 ε Z -> qf Z q1 ε Z -> qf Z

AceitaçãoEstado finalPilha vaziaEntrada, vazia para ε

O topo da pilha está à esquerda. Aceitar exige consumir toda a entrada. Mudar o critério não converte a máquina.

ExecutarPassoReiniciarVerificar exemplos

Palavra aceite.

Percurso aceitante

Passo	Estado	Por ler	Pilha, topo à esquerda
0	q0	aabb	Z
1	q0	abb	AZ
2	q0	bb	AAZ
3	q1	b	AZ
4	q1	ε	Z
5	qf	ε	Z

Limites da pesquisa

A pesquisa segue todos os ramos por níveis, até 128 transições por ramo, 96 símbolos na pilha e 5 000 configurações distintas. Um ramo aceitante basta para aceitar. Só se rejeita depois de esgotar as configurações alcançáveis sem encontrar aceitação. Atingir um limite deixa o resultado por decidir, mesmo que os ramos já observados não aceitem. Configurações repetidas são exploradas uma vez.

O vídeo de Rodrigo Dias complementa o estudo de autómatos de pilha e linguagens livres de contexto:

Abrir no YouTube

Contagens dentro de um intervalo

Para $\{a^nb^m\mid n\le m\le2n\}$, cada $a$ pode corresponder a um ou dois $b$. Um PDA escolhe empilhar um ou dois marcadores por $a$ e depois retira um por cada $b$. Com topo $X$, as escolhas são $a,X/AX$ e $a,X/AAX$. A mudança para a fase dos $b$ impede voltar a ler $a$.

Na palavra $aabbb$, um ramo empilha um marcador pelo primeiro $a$ e dois pelo segundo. A pilha fica $AAAZ$, que os três $b$ esvaziam até ao fundo. Em $aaabb$, todos os ramos têm pelo menos três marcadores, por isso dois $b$ nunca chegam. Em $aabbbbb$, todos têm no máximo quatro, pelo que cinco $b$ não podem ser lidos.

A CFG correspondente é $S\to aSb\mid aSbb\mid\varepsilon$. Com $n$ passos recursivos, escolhes $n$ contribuições de um ou dois $b$, dando qualquer total entre $n$ e $2n$. Para $aabbb$, podes derivar $S\Rightarrow aSb\Rightarrow aaSbbb\Rightarrow aabbb$.

Escolher uma fase e conservar a escolha

Comparar a quantidade de letras não determina quais podem aparecer na segunda fase. Considera um PDA por estado final, com início $p$, pilha inicial $Z$ e único final $f$, sem saídas. Em $p$, cada $a$ empilha um $A$. O primeiro $b$ passa para $q$, que só retira marcadores com $b$; o primeiro $c$ passa para $r$, que só os retira com $c$.

Não existem outras transições. $q$ e $r$ podem chegar a $f$ por $\varepsilon$ com $Z$ no topo, conservando esse fundo. A linguagem é

$$\{a^nb^n\mid n\ge1\}\ \cup\ \{a^nc^n\mid n\ge1\}.$$

Em $aabc$, depois dos dois $a$ a pilha é $AAZ$. O $b$ retira um marcador e escolhe $q$, ficando $(q,c,AZ)$. Não há transição por $c$ em $q$, por isso rejeita, embora existam dois símbolos depois dos dois $a$. Já $aabb$ e $aacc$ chegam ao final com entrada consumida e apenas $Z$ na pilha.

A palavra vazia é rejeitada: $p$ não é final e não tem transição vazia para $f$. Isso explica $n\ge1$. Se fundirmos $q,r$ numa fase que permite tanto $b$ como $c$ a cada remoção, obtemos $\{a^nu\mid n\ge1,\ u\in\{b,c\}^n\}$, que aceita $aabc$. Escolher um ramo uma vez é diferente de escolher a letra de cada passo.

Escolhas que a pilha não resolve

Para palíndromos pares $\{ww^R\mid w\in\{0,1\}^*\}$, empilha a primeira parte e escolhe, por uma transição vazia, quando começar a comparar. A partir daí, cada letra tem de ser igual ao topo, que é retirado. Aceita ao chegar ao fundo depois de consumir a entrada.

O meio não está marcado, por isso o PDA usa não determinismo para escolher a divisão. Para $0110$, um ramo empilha $01$, muda de fase e compara $10$. Os ramos que escolhem um meio errado falham. Com um separador, $w\#w^R$, a letra $\#$ indica quando mudar de fase.

Um PDA determinístico tem no máximo uma escolha por condição e não permite, para o mesmo estado e topo, concorrer uma transição vazia com uma transição que lê entrada. Ao contrário do caso finito, PDA determinísticos e não determinísticos não têm o mesmo poder: as linguagens livres de contexto determinísticas são uma subclasse própria das livres de contexto.

Trocar o critério de aceitação

Os critérios têm o mesmo poder para PDA não determinísticos, mas mudar o critério de uma máquina existente pode mudar a linguagem. É preciso construir outra máquina.

De pilha vazia para estado final, coloca um fundo novo $\bot$ abaixo da pilha simulada. Um estado inicial novo transforma $\bot$ em $Z_0\bot$. Quando o simulador expõe $\bot$, entra num final novo. Só uma computação que consumiu toda a entrada é aceite.

De estado final para pilha vazia, usa também um fundo novo, para impedir esvaziamento acidental durante a simulação. De cada antigo final, permite passar para um estado que retira todos os símbolos, incluindo o fundo, por transições vazias. Se ainda houver entrada, esse ramo não consegue consumi-la e não aceita.

Esta equivalência não se aplica sem alterações às convenções determinísticas; as transições vazias acrescentadas podem criar escolhas.

Conversões de critério com transições concretas

Toma uma máquina por pilha vazia que só tem $\delta(q_0,a,Z_0)=\{(q_1,\varepsilon)\}$. Ela aceita exatamente $\{a\}$: lê $a$ e retira $Z_0$. Não há outras transições.

Na máquina por estado final, acrescenta fundo $\bot$, início $p_0$ e único final $p_f$. Usa $\delta(p_0,\varepsilon,\bot)=\{(q_0,Z_0\bot)\}$, conserva a transição antiga e, para cada estado simulado $q$, acrescenta $\delta(q,\varepsilon,\bot)=\{(p_f,\bot)\}$. O final não tem saídas.

Para $a$:

$$(p_0,a,\bot)\vdash(q_0,a,Z_0\bot) \vdash(q_1,\varepsilon,\bot)\vdash(p_f,\varepsilon,\bot).$$

Para $aa$, o mesmo percurso termina em $(p_f,a,\bot)$. A entrada restante impede aceitar. O fundo novo distingue esvaziar a pilha simulada de esvaziar toda a pilha da máquina nova.

De estado final para pilha vazia, usa um fundo novo $\bot$ e um estado de limpeza $p_e$. De cada antigo final $f$, acrescenta $(f,\varepsilon,X) \to (p_e,\varepsilon)$ para todo o $X$ da pilha, e em $p_e$ retira todos os símbolos até $\bot$ inclusive. Se a máquina antiga aceita $aabb$ em $q_f$ com pilha $Z$, a nova consome $aabb$, passa a $p_e$ e esvazia $Z\bot$. Se chega a $q_f$ com entrada restante, $p_e$ não consegue consumir essa entrada e o ramo falha.

De CFG para PDA

Um PDA por pilha vazia pode simular derivações mais à esquerda. A pilha começa com $S$ e contém variáveis e terminais:

• para cada produção $A\to\alpha$, permite substituir $A$ no topo por $\alpha$, sem ler entrada;
• para cada terminal $a$, permite ler $a$ e retirar $a$ do topo.

Para $S\to aSb\mid\varepsilon$, o ramo que aceita $ab$ é:

$$(q,ab,S)\vdash(q,ab,aSb)\vdash(q,b,Sb) \vdash(q,b,b)\vdash(q,\varepsilon,\varepsilon).$$

A expansão mantém na pilha a parte ainda por gerar, com a primeira posição no topo. Numa implementação que empilhe símbolos um a um, tens de os inserir da direita para a esquerda para obter esse mesmo topo.

De PDA para CFG

Ver a construção com variáveis indexadas por estados

Primeiro coloca o PDA no critério de pilha vazia. A variável $[pXq]$ descreve as palavras que levam do estado $p$ ao estado $q$ removendo o marcador $X$, sem tocar no que estava abaixo dele.

Para cada estado $q$, acrescenta $S\to[q_0Z_0q]$. Se uma transição lê $a$, vai de $p$ para $r$ e retira $X$, acrescenta $[pXr]\to a$, podendo $a$ ser $\varepsilon$.

Se a transição substitui $X$ por um único $Y$, acrescenta $[pXq]\to a[rYq]$ para cada estado $q$. A variável seguinte acompanha a remoção de $Y$.

Se a transição substitui $X$ por $YZ$, a remoção futura tem duas partes: remover $Y$ até algum estado intermédio $s$, depois remover $Z$ até $q$. Para todos os estados $s,q$, acrescenta

$$[pXq]\to a[rYs][sZq].$$

Se empilhar mais símbolos, usa uma variável por símbolo e estados intermédios para ligar as etapas. A gramática gera precisamente as entradas que esvaziam a pilha.

PDA para CFG num exemplo pequeno

Considera um PDA por pilha vazia com estados $p,q$, $Z_0$ inicial e cinco transições:

• $\delta(p,a,Z_0)=\{(p,AZ_0)\}$;
• $\delta(p,a,A)=\{(p,AA)\}$;
• $\delta(p,b,A)=\{(q,\varepsilon)\}$;
• $\delta(q,b,A)=\{(q,\varepsilon)\}$;
• $\delta(q,\varepsilon,Z_0)=\{(q,\varepsilon)\}$.

A última transição esvazia o fundo no fim; sem ela, $ab$ deixaria $Z_0$ na pilha e não seria aceite por pilha vazia. Com as cinco transições, a máquina reconhece $\{a^nb^n \mid n \ge 1\}$.

A variável $[pXq]$ gera as palavras que levam de $p$ a $q$ removendo o $X$ do topo sem tocar no que está abaixo. Aplicando a construção geral a cada transição:

• $S \to [pZ_0p] \mid [pZ_0q]$;
• empilhar $Z_0\to AZ_0$ por $a$ de $p$ para $p$ dá, para todos $s,t$ em $\{p,q\}$: $[pZ_0t] \to a[pAs][sZ_0t]$, ou seja as quatro produções com $t=p,q$ e $s=p,q$;
• empilhar $A\to AA$ por $a$ de $p$ para $p$ dá, para todos $s,t$ em $\{p,q\}$: $[pAt] \to a[pAs][sAt]$, ou seja as quatro produções com $t=p,q$ e $s=p,q$;
• $[pAq] \to b$ e $[qAq] \to b$, pelas duas transições que retiram $A$ lendo $b$;
• $[qZ_0q] \to \varepsilon$, pela transição que esvazia o fundo.

Para $ab$, fixa o estado intermédio $s=q$: $S \Rightarrow [pZ_0q] \Rightarrow a[pAq][qZ_0q] \Rightarrow ab[qZ_0q] \Rightarrow ab$. A primeira produção usa a transição $Z_0\to AZ_0$ com $s=q$; $[pAq]\to b$ consome o $b$; $[qZ_0q]\to\varepsilon$ esvazia o fundo. Cada variável regista onde começa e acaba a remoção de um marcador, e o $s$ quantificado liga as duas metades de $AZ_0$.

Com a conversão inversa, isto prova: uma linguagem é livre de contexto se e só se algum PDA a reconhece.