Exercício 6. Um PDA é chamado restrito se, em qualquer transição, ele pode aumentar a altura da pilha por no máximo um símbolo, ou seja, para
conter
deve ocorrer
. Mostre que se
é um
, então existe um PDA restrito
tal que
.
Passo 1
O enunciado pede para provar que, dado um PDA qualquer
, podemos construir um PDA “restrito”
equivalente, ou seja, com a mesma linguagem
, em que toda transição faz pelo menos uma leitura de entrada ou
e substitui o símbolo do topo da pilha por uma palavra de tamanho no máximo 2.
Conteúdo: transformações em autômatos de pilha. Vamos usar a ideia de simular toda transição que empurre muitos símbolos por uma cadeia de transições que empurra dois símbolos por vez, introduzindo estados e símbolos auxiliares.
Conteúdo: transformações em autômatos de pilha. Vamos usar a ideia de simular toda transição que empurre muitos símbolos por uma cadeia de transições que empurra dois símbolos por vez, introduzindo estados e símbolos auxiliares.
Passo 2
Considere uma transição qualquer de
do tipo
onde
e
. Em
essa transição retira
do topo da pilha e empilha
de uma só vez. Para obedecer a restrição
, vamos substituir essa única transição por uma cadeia de transições em
que empurra, em cada passo, no máximo dois símbolos:
- criaremos
estados novos , - criaremos
símbolos novos de pilha .
O esquema de simulação será:
Em cada uma dessas transições, o número de símbolos empurrados é 2 (nos primeiros
passos) ou 1 (no último), satisfazendo
.
Passo 3
Definição formal de
. Se
é o PDA original, defina
onde
O conjunto de transições
é obtido de
da seguinte forma:
- toda transição
com entra em sem alterações; - toda transição com
, , é substituída pelo bloco de transições descrito no Passo 2.
Não há outra modificação: mesma função de aceitação e símbolo inicial.
Passo 4
Argumento de correção e equivalência de linguagem.
- Qualquer computação de
que use uma transição de empurrar símbolos pode ser “desdobrada” em usando exatamente a cadeia de transições que simulam aquele empurrão de uma só vez. Essas transições não consomem símbolos de entrada além do primeiro (as demais são ); portanto, aceita a mesma sequência de entrada. - Inversamente, toda sequência de movimentos em
que simula blocos auxiliares pode ser “compactada” em um único passo de , de volta ao empurrão original de . Transições que não foram subdivididas continuam idênticas. - Como não mudamos a condição de aceitação nem o resto da máquina, conclui-se que
Além disso, por construção, cada transição de
empurra no máximo dois símbolos, logo
é um PDA restrito.
Resposta
O PDA restrito
construído acima satisfaz
e em cada transição empurra no máximo dois símbolos, conforme exigido.