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 \delta(q, a, Z) conter (p, \gamma) deve ocorrer |\gamma| \leq 2. Mostre que se P é um P D A, então existe um PDA restrito P_{3} tal que L(P)=L\left(P_{3}\right).

Passo 1

O enunciado pede para provar que, dado um PDA qualquer P, podemos construir um PDA “restrito” P_{3} equivalente, ou seja, com a mesma linguagem L(P)=L(P_{3}), em que toda transição faz pelo menos uma leitura de entrada ou \varepsilon 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.

Passo 2

Considere uma transição qualquer de P do tipo
\delta(q,a,A)\;\ni\;(p,\;\gamma),
onde \gamma=\gamma_{1}\gamma_{2}\cdots\gamma_{n} e n>2. Em P essa transição retira A do topo da pilha e empilha \gamma_{1}\gamma_{2}\dots\gamma_{n} de uma só vez. Para obedecer a restrição |\gamma|\le2, vamos substituir essa única transição por uma cadeia de transições em P_{3} que empurra, em cada passo, no máximo dois símbolos:
  1. criaremos n-1 estados novos q_{1},q_{2},\dots,q_{n-1},
  2. criaremos n-2 símbolos novos de pilha Y_{1},Y_{2},\dots,Y_{n-2}.
O esquema de simulação será:
\begin{aligned} &\delta'(q,a,A)\;\ni\;(q_{1},\,\gamma_{1}Y_{1}),\\\ &\delta'(q_{1},\varepsilon,Y_{1})\;\ni\;(q_{2},\,\gamma_{2}Y_{2}),\\\ &\quad\vdots\\\ &\delta'(q_{n-2},\varepsilon,Y_{n-2})\;\ni\;(q_{n-1},\,\gamma_{n-1}Y_{n-1}),\\\ &\delta'(q_{n-1},\varepsilon,Y_{n-1})\;\ni\;(p,\,\gamma_{n}). \end{aligned}
Em cada uma dessas transições, o número de símbolos empurrados é 2 (nos primeiros n-1 passos) ou 1 (no último), satisfazendo \le2.

Passo 3

Definição formal de P_{3}. Se
P=(Q,\Sigma,\Gamma,\delta,q_{0},Z_{0},F)
é o PDA original, defina
P_{3}=(Q',\Sigma,\Gamma',\delta',q_{0},Z_{0},F),
onde
Q'=Q\;\cup\;\{\,q_{i}\mid \text{para cada transição com }n>2,\;1\le i\le n-1\},çã
\Gamma'=\Gamma\;\cup\;\{\,Y_{j}\mid \text{para cada variedade de comprimentos}>2,\;1\le j\le n-2\}.
O conjunto de transições \delta' é obtido de \delta da seguinte forma:
  • toda transição \delta(q,a,A)\ni(p,\gamma) com |\gamma|\le2 entra em \delta' sem alterações;
  • toda transição com \gamma=\gamma_{1}\dots\gamma_{n}, n>2, é 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.
  1. Qualquer computação de P que use uma transição de empurrar n>2 símbolos pode ser “desdobrada” em P_{3} usando exatamente a cadeia de n 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 \varepsilon); portanto, P_{3} aceita a mesma sequência de entrada.
  2. Inversamente, toda sequência de movimentos em P_{3} que simula blocos auxiliares pode ser “compactada” em um único passo de P, de volta ao empurrão original de \gamma. Transições que não foram subdivididas continuam idênticas.
  3. Como não mudamos a condição de aceitação nem o resto da máquina, conclui-se que
L(P_{3})=L(P).
Além disso, por construção, cada transição de \delta' empurra no máximo dois símbolos, logo P_{3} é um PDA restrito.

Resposta

O PDA restrito P_{3} construído acima satisfaz L(P_{3})=L(P) e em cada transição empurra no máximo dois símbolos, conforme exigido.

Exercícios relacionados