Exercício 7. Prove o seguinte teorema comentado em sala:
é a linguagem para algum
, então existe um
tal que
.
Passo 1
O enunciado pertence ao conteúdo de autômatos com pilha (PDA) e modos de aceitação. Temos um PDA
que aceita uma linguagem
por estado final. Queremos construir um PDA
que aceita a mesma linguagem por pilha vazia, ou seja, provar que existe
tal que
Passo 2
Defina
. Vamos construir
que aceita por pilha vazia. Os componentes são:
–
.
– , onde
é um novo símbolo de fundo de pilha.
– Estado inicial e fundo de pilha
.
–
– Estado inicial
Agora as transições
:
- Na configuração inicial empurramos
(fundo original) sobre e vamos para :
- Para cada transição
de em , copiamos em :
- Sempre que
, adicionamos uma transição para um estado de limpeza , sem ler entrada e sem empilhar nada extra:
- No estado
descartamos toda a pilha até chegar em . Ou seja, para cada :
e quando chegar em
fazemos
esvaziando a pilha por completo.
Passo 3
Prova de
. Seja
. Então existe uma sequência de transições em
que, ao ler
de
com pilha iniciada em
, termina em algum
com qualquer pilha
. Em
executamos primeiro a transição de
que empilha
e vai a
, então simulamos exatamente os mesmos passos de
, chegando em
com pilha
. Aí usamos a transição
para
e esvaziamos
e depois
. O resultado é pilha vazia após ler toda a palavra
. Logo
.
Passo 4
Prova de
. Seja
. Então em
há um caminho que, começando em
, esvazia a pilha. A única forma de remover
é alcançar o estado
, o qual só é acessível por uma transição
vinda de algum
. Antes disso,
apenas simula
de
. Logo, ao chegar em
a ler toda a entrada, temos a simulação exata de uma aceitação por estado final em
. Portanto
.
Resposta
Construímos
acrescentando um novo símbolo de fundo de pilha e um estado de limpeza que é acionado apenas em estados finais de
, e mostramos as duas inclusões
e
. Assim