Exercício 8. Na prova de que existe um PDA com aceitação por estado final P_{F} para todo PDA com aceitação por pilha vazia P_{N} criamos um P_{F} a partir de P_{N} e provamos que L\left(P_{F}\right)=N\left(P_{N}\right). Para tal foi provado que se w \in N\left(P_{N}\right), então w \in L\left(P_{F}\right). Prove diretamente a contrapositiva: Se w \notin L\left(P_{F}\right), então w \notin N\left(P_{N}\right).

Passo 1

O enunciado nos pede para mostrar diretamente a contrapositiva da afirmação
w\in N(P_{N})\;\Longrightarrow\;w\in L(P_{F}),
isto é, provar
w\notin L(P_{F}) \;\Longrightarrow\; w\notin N(P_{N}).
Aqui P_{N}=(Q_{N},\Sigma,\Gamma_{N},\delta_{N},q_{0_{N}},Z_{0_{N}}) é o PDA que aceita por pilha vazia, e P_{F} é o PDA que aceitaria pela finalização em um novo estado q_{f}, construído a partir de P_{N} acrescentando:
1. um novo símbolo de fundo de pilha Z_{0}',
2. um novo estado inicial q_{s} com transição
\delta_{F}(q_{s},\varepsilon,Z_{0}')\ni(q_{0_{N}},Z_{0_{N}}\,Z_{0}'),
3. um novo estado final q_{f} com, para todo p\in Q_{N}, a transição
\delta_{F}(p,\varepsilon,Z_{0}')\ni(q_{f},\varepsilon).

Passo 2

Descrevemos como P_{F} simula P_{N} e reconhece exatamente as mesmas cadeias que P_{N} aceita por pilha vazia:
  • Partindo de (q_{s},w,Z_{0}'), P_{F} faz uma transição- \epsilon para (q_{0_{N}},w,Z_{0_{N}}\,Z_{0}').
  • Em seguida, reproduce passo a passo qualquer sequência de movimentos de P_{N}, mantendo Z_{0}' no fundo da pilha.
  • Quando P_{N} chega a esvaziar sua pilha (restando só Z_{0_{N}}), ela é também esvaziada por essa simulação, deixando apenas Z_{0}'.
  • Então P_{F} faz uma transição- \epsilon de qualquer configuração (p,\varepsilon,Z_{0}') para (q_{f},\varepsilon,\varepsilon), aceitando em q_{f}.

Passo 3

Agora provamos a contrapositiva. Suponha
w\notin L(P_{F}).
Queremos mostrar w\notin N(P_{N}). Se por absurdo w\in N(P_{N}), então existe em P_{N} uma sequência de configurações
(q_{0_{N}},\,w,\,Z_{0_{N}}) \;\xRightarrow[\!*]{} \; (q',\,\varepsilon,\,\varepsilon).
A construção acima garante que P_{F} pode reproduzir exatamente essas mesmas transições de \delta_{N}, precedidas pela primeira ação- \epsilon que empilha Z_{0_{N}} sobre Z_{0}', e terminadas pela ação- \epsilon que desempilha Z_{0}' indo para q_{f}. Logo haveria em P_{F} uma derivação
(q_{s},\,w,\,Z_{0}') \;\xRightarrow[\!*]{} \; (q_{f},\,\varepsilon,\,\varepsilon),
o que implicaria w\in L(P_{F}), contradizendo a hipótese w\notin L(P_{F}).

Resposta

Portanto, concluímos diretamente que
w\notin L(P_{F}) \;\Longrightarrow\; w\notin N(P_{N}).

Exercícios relacionados