Exercício 7. Prove o seguinte teorema comentado em sala: S e L\left(P_{F}\right) é a linguagem para algum P D A P_{F}, então existe um P D A P_{N} tal que L\left(P_{F}\right)=N\left(P_{N}\right).

Passo 1

O enunciado pertence ao conteúdo de autômatos com pilha (PDA) e modos de aceitação. Temos um PDA P_{F} que aceita uma linguagem L(P_{F}) por estado final. Queremos construir um PDA P_{N} que aceita a mesma linguagem por pilha vazia, ou seja, provar que existe P_{N} tal que
N(P_{N}) \;=\; L(P_{F})\,.

Passo 2

Defina P_{F}=(Q,\Sigma,\Gamma,\delta,q_{0},Z_{0},F). Vamos construir
P_{N}=(Q',\Sigma,\Gamma',\delta',q_{s}',Z_{0}')
que aceita por pilha vazia. Os componentes são:
Q'=Q\cup\{q_{s}',q_{\mathrm{clean}}\}.
\Gamma'=\Gamma\cup\{Z_{0}'\}, onde Z_{0}' é um novo símbolo de fundo de pilha.
– Estado inicial q_{s}' e fundo de pilha Z_{0}'.
Agora as transições \delta':
  1. Na configuração inicial empurramos Z_{0} (fundo original) sobre Z_{0}' e vamos para q_{0}:
\delta'(q_{s}',\varepsilon,Z_{0}') \ni (q_{0},Z_{0}Z_{0}')\,.
  1. Para cada transição (p,a,A)\mapsto (q,\alpha) de \delta em P_{F}, copiamos em \delta':
\delta'(p,a,A)\ni (q,\alpha)\,.
  1. Sempre que p\in F, adicionamos uma transição \varepsilon para um estado de limpeza q_{\mathrm{clean}}, sem ler entrada e sem empilhar nada extra:
\delta'(p,\varepsilon,Z)\ni (q_{\mathrm{clean}},Z) \quad\text{para todo }Z\in\Gamma'\,.
  1. No estado q_{\mathrm{clean}} descartamos toda a pilha até chegar em Z_{0}'. Ou seja, para cada A\in\Gamma:
\delta'(q_{\mathrm{clean}},\varepsilon,A)\ni (q_{\mathrm{clean}},\varepsilon)
e quando chegar em Z_{0}' fazemos
\delta'(q_{\mathrm{clean}},\varepsilon,Z_{0}')\ni (q_{\mathrm{clean}},\varepsilon)\,,
esvaziando a pilha por completo.

Passo 3

Prova de L(P_{F})\subseteq N(P_{N}). Seja w\in L(P_{F}). Então existe uma sequência de transições em P_{F} que, ao ler w de q_{0} com pilha iniciada em Z_{0}, termina em algum p\in F com qualquer pilha \gamma. Em P_{N} executamos primeiro a transição de q_{s}' que empilha Z_{0}Z_{0}' e vai a q_{0}, então simulamos exatamente os mesmos passos de P_{F}, chegando em p\in F com pilha \gamma Z_{0}'. Aí usamos a transição \varepsilon para q_{\mathrm{clean}} e esvaziamos \gamma e depois Z_{0}'. O resultado é pilha vazia após ler toda a palavra w. Logo w\in N(P_{N}).

Passo 4

Prova de N(P_{N})\subseteq L(P_{F}). Seja w\in N(P_{N}). Então em P_{N} há um caminho que, começando em (q_{s}',w,Z_{0}'), esvazia a pilha. A única forma de remover Z_{0}' é alcançar o estado q_{\mathrm{clean}}, o qual só é acessível por uma transição \varepsilon vinda de algum p\in F. Antes disso, P_{N} apenas simula \delta de P_{F}. Logo, ao chegar em p\in F a ler toda a entrada, temos a simulação exata de uma aceitação por estado final em P_{F}. Portanto w\in L(P_{F}).

Resposta

Construímos P_{N} acrescentando um novo símbolo de fundo de pilha e um estado de limpeza que é acionado apenas em estados finais de P_{F}, e mostramos as duas inclusões L(P_{F})\subseteq N(P_{N}) e N(P_{N})\subseteq L(P_{F}). Assim
L(P_{F}) \;=\; N(P_{N})\,.

Exercícios relacionados