Autómatos de pilha

Modelo

PDA: estados finitos mais pilha. Transição escolhe por estado, letra ou ε e topo; substitui o topo por uma sequência. Topo à esquerda: $X$ por $YZ$ deixa $Y$ no topo; por $\varepsilon$ retira $X$.

• $a,X/\alpha$: lê $a$, substitui $X$ por $\alpha$. Com $a=\varepsilon$, não consome mas exige o topo.
• Configuração $(q,w,\gamma)$: estado, entrada restante, pilha. $(q,aw,X\beta)\vdash(p,w,\alpha\beta)$ se $(p,\alpha)\in\delta(q,a,X)$.

Aceitação

Um PDA aceita quando existe um ramo que consome toda a entrada e cumpre o critério. Encontrar um ramo que chega a um final, ou que esvazia a pilha, antes de consumir tudo não chega.

Critério	O ramo aceitante termina com
Estado final	Entrada consumida e estado em $F$; a pilha pode conservar símbolos
Pilha vazia	Entrada consumida e pilha vazia; o estado não importa

Os dois critérios têm o mesmo poder para PDA não determinísticos, mas é preciso construir outra máquina para trocar o critério. Mudar o critério na mesma máquina pode mudar a linguagem. Os PDA determinísticos têm menos poder que os não determinísticos.

Contagens e palíndromos

Para $\{a^nb^n\mid n\ge0\}$, com $n$ a contar os pares: empilha $A$ por cada $a$, muda de fase no primeiro $b$ e retira um $A$ por cada $b$. A palavra vazia é aceite pela transição vazia desde o início, sem ler nada. Em $aabb$ a pilha passa por $Z,AZ,AAZ,AZ,Z$ e o ramo aceitante termina com a entrada consumida e $Z$ exposto. Ver só $Z$ no topo a meio da palavra não prova nada: $aab$ sobra marcador, $abb$ bloqueia e $aba$ quebra a ordem.

• Intervalo $n\le m\le2n$: empilha um ou dois marcadores por $a$; CFG $S\to aSb\mid aSbb\mid\varepsilon$.
• Palíndromo par $ww^R$: empilha a primeira metade, adivinha o meio por ε, compara retirando. Com separador $w\#w^R$, o $\#$ marca a mudança.

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.

Conversões

• Troca de critério: para passar de pilha vazia a estado final, põe um fundo novo abaixo da pilha e aceita quando ele fica exposto depois de consumir tudo; no sentido inverso, usa fundo novo e uma fase de limpeza desde os antigos finais. Em ambos os casos, só conta quando a entrada está consumida.
• CFG para PDA: começa com $S$ no topo. Cada produção $A\to\alpha$ dá uma transição $\varepsilon$ que substitui a variável $A$ no topo pelo lado direito $\alpha$, sem ler entrada. Cada terminal $a$ dá uma transição que lê $a$ quando $a$ está no topo e o retira. Empilha o lado direito da direita para a esquerda para manter a ordem.
• PDA para CFG: a variável $[pXq]$ gera as palavras que levam de $p$ a $q$ removendo o $X$ do topo, sem mexer na pilha que está abaixo de $X$. Se $(r,YZ)\in\delta(p,a,X)$: $[pXt]\to a[rYs][sZt]$ para todos os estados $s,t$. Se $(r,\varepsilon)\in\delta(p,a,X)$: $[pXr]\to a$.

Uma linguagem é CFL se e só se algum PDA não determinístico a reconhece.

Escolha de fase

Empilhar por $a$ e escolher uma fase só de $b$ ou só de $c$ dá $\{a^nb^n\mid n\ge1\}\cup\{a^nc^n\mid n\ge1\}$: $aabc$ bloqueia em $(q,c,AZ)$. Fundir as fases numa só, que aceita $b$ ou $c$ em cada remoção, dá $\{a^nu\mid n\ge1,\ u\in\{b,c\}^n\}$, que aceita $aabc$. A contagem não substitui a restrição das letras.

Construção completa de PDA para CFG.