Exercício 10. Dada a Linguagem L_{\text {pal }}\left\{w \in\{0,1\}^{*}\right. : onde w=w^{R} (palíndromo)}, faça o seguinte:
  1. Construa um PDA para a linguagem L_{\text {pal }} com aceitação por estado final;
  2. Utilizando algoritmo visto em sala, transforme o PDA do item anterior para um PDA com aceitação por pilha vazia;
  3. Utilizando algoritmo visto em sala, gere uma G L C^{1} a partir do autômato do item anterior.

Passo 1

O enunciado pede para mostrar como a linguagem dos palíndromos sobre o alfabeto \{0,1\} é gerada por um PDA e, em seguida, por um GLC. O conteúdo envolvido é teoria de autômatos de pilha e gramáticas livres de contexto. Vamos:
1. Construir um PDA M_1 que aceite L_{\text{pal}} por estado final.
2. Aplicar a construção que converte aceitação por estado final em aceitação por pilha vazia, obtendo M_2.
3. Usar o algoritmo de conversão de PDA para GLC para gerar uma gramática G que reconheça L_{\text{pal}}.

Passo 2

Construção de M_1=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F) que aceita palíndromos por estado final:
\Sigma=\{0,1\}, \Gamma=\{0,1,Z_0\}, Q=\{q_0,q_1,q_2\}, F=\{q_2\}. Transições \delta:
\begin{aligned} &\delta(q_0,0,X) = (q_0,0X),\quad \delta(q_0,1,X) = (q_0,1X)\quad\text{para }X\in\{0,1,Z_0\},\\\ &\delta(q_0,\varepsilon,X) = (q_1,X)\quad\text{(não determinístico: começo da parte de espelho)},\\\ &\delta(q_1,0,0) = (q_1,\varepsilon),\quad \delta(q_1,1,1) = (q_1,\varepsilon),\\\ &\delta(q_1,\varepsilon,Z_0) = (q_2,Z_0)\quad\text{(quando toda a pilha voltar ao símbolo inicial)}. \end{aligned}ãíçí
Intuição: em q_0 empilhamos os símbolos da primeira metade; transição \varepsilon vai para q_1; em q_1 cada símbolo lido deve casar com o topo da pilha; ao esvaziar de volta em Z_0 chegamos em q_2 (final).

Passo 3

Transformação de M_1 em M_2 que aceita por pilha vazia. Seja M_2=(Q',\Sigma,\Gamma',\delta',p_0,Z_0',\varnothing) onde
Q'=Q\cup\{p_0,p_f\},\quad \Gamma'=\Gamma\cup\{Z_0'\}.
Definimos \delta' assim:
\begin{aligned} &\delta'(p_0,\varepsilon,Z_0') = (q_0,Z_0\,Z_0'),\\\ &\delta'\bigl(p,\;a,\;A\bigr) = \delta(p,a,A)\quad\text{para todas as transições de }M_1,\\\ &\delta'(q_2,\varepsilon,Z_0') = (p_f,Z_0'),\\\ &\delta'(p_f,\varepsilon,Z_0') = (p_f,\varepsilon). \end{aligned}çõ
Não há estados finais em M_2; aceita-se quando a pilha ficar vazia em p_f.

Passo 4

Aplicando o algoritmo de conversão de PDA vazio \toGLC, obtemos a gramática G=(V,\Sigma,P,S). O único não terminal inicial é
S = [\,p_0 Z_0' p_f\,],
e as produções correspondem às transições de M_2. O resultado simplificado (sabendo que a linguagem são todos os palíndromos) é a gramática padrão:
\begin{aligned} S &\to 0\,S\,0\;\mid\;1\,S\,1\;\mid\;0\;\mid\;1\;\mid\;\varepsilon. \end{aligned}

Resposta

PDA por estado final M_1\): \[Q=\{q_0,q_1,q_2\},\;\Sigma=\{0,1\},\;\Gamma=\{0,1,Z_0\},\;q_0\text{ start},\;F=\{q_2\},
\begin{cases} \delta(q_0,0,X)=(q_0,0X),&\delta(q_0,1,X)=(q_0,1X),\\\ \delta(q_0,\varepsilon,X)=(q_1,X),&\delta(q_1,0,0)=(q_1,\varepsilon),\\\ \delta(q_1,1,1)=(q_1,\varepsilon),&\delta(q_1,\varepsilon,Z_0)=(q_2,Z_0). \end{cases}
PDA por pilha vazia (M_2]:
Q'=Q\cup\{p_0,p_f\},\;\Gamma'=\Gamma\cup\{Z_0'\},\;p_0\text{ start},\;\text{aceita quando pilha vazia,}
\begin{cases} \delta'(p_0,\varepsilon,Z_0')=(q_0,Z_0Z_0'),\\\ \delta'(p,\;a,\;A)=\delta(p,a,A)\;\forall p\in Q,\;a\in\{0,1,\varepsilon\},\;A\in\Gamma,\\\ \delta'(q_2,\varepsilon,Z_0')=(p_f,Z_0'),\\\ \delta'(p_f,\varepsilon,Z_0')=(p_f,\varepsilon). \end{cases}
Gramática G (GLC ^1) gerada:
V=\{S\},\;\Sigma=\{0,1\},\;S\text{ start},
S \;\to\; 0\,S\,0 \;\mid\; 1\,S\,1 \;\mid\; 0 \;\mid\; 1 \;\mid\; \varepsilon.

Exercícios relacionados