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:
Construa um PDA para a linguagem L_{\text {pal }} com aceitação por estado final;
Utilizando algoritmo visto em sala, transforme o PDA do item anterior para um PDA com aceitação por pilha vazia;
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