Autômatos com Pilha

Um autômato com pilha é um reconhecedor com controle finito e uma pilha: memória LIFO ilimitada da qual só o topo entra na transição. O modelo padrão é o APND, a 7-upla (Q, Σ, Γ, δ, q₀, Z₀, F).

Execução, conversão GLC↔APND, bombeamento e CYK deste tópico — e duas pilhas na máquina de Turing — partem dessa 7-upla.

As páginas se agrupam em quatro blocos. O primeiro monta a máquina: escreve δ(q, a, X), desenha o diagrama e percorre configurações até aceitar por estado final ou por pilha vazia.

O segundo converte GLC em APND e APND em GLC, e distingue APD de APND.

O terceiro aplica o lema do bombeamento na fatia uvwxy e lê quais operações preservam a classe.

O quarto decide sim ou não sobre a gramática: pertencimento pela tabela CYK, vacuidade por variáveis úteis, finitude de L(G).

Montar δ e aceitar uma cadeia por execução está em Definições. Converter G em APND, ou o inverso, e separar APD de APND com {wwᴿ} está em Relação entre AP e GLC.

{wwᴿ} é livre de contexto e fica fora das livres de contexto determinísticas em Relação entre AP e GLC. {aⁿbⁿcⁿ} sai das livres de contexto pelo bombeamento uvⁱwxⁱy em Propriedades das Linguagens Livres de Contexto.

Aceitar w percorrendo configurações do APND está em Definições. Decidir se w pertence a L(G) pela tabela CYK está em Algoritmos de Decisão.

O lema e o fechamento sob interseção estão em Propriedades das Linguagens Livres de Contexto. Vacuidade por símbolos úteis e finitude de L(G) estão em Algoritmos de Decisão.