Exercício 8. Na prova de que existe um PDA com aceitação por estado final
para todo PDA com aceitação por pilha vazia
criamos um
a partir de
e provamos que
. Para tal foi provado que se
, então
. Prove diretamente a contrapositiva: Se
, então
.
Passo 1
O enunciado nos pede para mostrar diretamente a contrapositiva da afirmação
isto é, provar
Aqui
é o PDA que aceita por pilha vazia, e
é o PDA que aceitaria pela finalização em um novo estado
, construído a partir de
acrescentando:
. um novo símbolo de fundo de pilha
,
. um novo estado inicial
com transição
,
. um novo estado final
com, para todo
, a transição
Passo 2
Descrevemos como
simula
e reconhece exatamente as mesmas cadeias que
aceita por pilha vazia:
- Partindo de
, faz uma transição- para . - Em seguida, reproduce passo a passo qualquer sequência de movimentos de
, mantendo no fundo da pilha. - Quando
chega a esvaziar sua pilha (restando só ), ela é também esvaziada por essa simulação, deixando apenas . - Então
faz uma transição- de qualquer configuração para , aceitando em .
Passo 3
Agora provamos a contrapositiva. Suponha
Queremos mostrar
. Se por absurdo
, então existe em
uma sequência de configurações
A construção acima garante que
pode reproduzir exatamente essas mesmas transições de
, precedidas pela primeira ação-
que empilha
sobre
, e terminadas pela ação-
que desempilha
indo para
. Logo haveria em
uma derivação
o que implicaria
, contradizendo a hipótese
.
Resposta
Portanto, concluímos diretamente que