Exercício 12. Prove que se L é uma LLC sobre alfabeto \Sigma e s é uma substituição de \Sigma tal que s(a) é uma L L C para todo a \in \Sigma, então s(L) é uma L L C.
Obs: Primeiro descreva como constrir uma G L C G_{s} para s(L) e depois prove que L\left(G_{s}\right)=s(L).

Passo 1

O enunciado afirma que L\subseteq\Sigma^* é uma linguagem livre de contexto (LLC) gerada por alguma gramática G sobre o alfabeto \Sigma, e que temos uma substituição
s:\Sigma\to\mathcal{P}(\Delta^*)
tal que, para cada símbolo terminal a\in\Sigma, a linguagem s(a)\subseteq\Delta^* também é uma LLC. Queremos mostrar que
s(L)\;=\;\bigcup_{u\in L}s(u)
é uma LLC. Para isso, primeiro vamos construir explicitamente uma gramática G_s que gere s(L), depois provamos que L(G_s)=s(L).

Passo 2

Sejam
G=(V,\Sigma,P,S)
uma gramática livre de contexto com L(G)=L, e, para cada a\in\Sigma,
G_a=(V_a,\Delta,P_a,S_a)
uma gramática livre de contexto com L(G_a)=s(a). Aqui \Delta é o alfabeto comum em que todas as s(a) estão definidas (pode ser a união dos alfabetos de cada G_a).

Passo 3

Definimos a nova gramática
G_s=\bigl(V\;\cup\!\!\!\bigcup_{a\in\Sigma}V_a\,,\;\Delta,\;P_s,\;S\bigr),
onde o conjunto de regras [P_s) é a união de duas partes:
  1. Para cada produção original A\to X_1X_2\cdots X_n \quad\text{em }P,onde cada X_i é ou um não-terminal de V ou um terminal a\in\Sigma, incluímos em P_s a produção A\;\to\;Y_1Y_2\cdots Y_n,em que Y_i=\begin{cases} X_i,&\text{se }X_i\in V,\\\ S_{X_i},&\text{se }X_i\in\Sigma\text{ (isto é, }X_i=a\text{).} \end{cases}é
  2. Todas as produções de cada (G_a], isto é,
    P_s\;\supseteq\;\bigcup_{a\in\Sigma}P_a.
O símbolo inicial de G_s permanece S.

Passo 4

Mostramos L(G_s)\subseteq s(L). Seja w\in L(G_s). Então existe derivação
S\;\xLongrightarrow[G_s]{*}\;w.
Fazemos indução sobre o número de passagens em que aplicamos regras do tipo 1 (as que vêm de P).
  • Base: se nenhuma regra do tipo 1 foi usada, a derivação ficou inteiramente dentro de algum G_a, mas não pode, pois S não é não-terminal de nenhum G_a.
  • Passo indutivo: na primeira vez que usamos uma produção de tipo 1, digamos A\;\to\;Y_1\cdots Y_ncujo trecho corresponde a uma produção original A\to X_1\cdots X_n em G. Até esse ponto a árvore de derivação corresponde a produzir alguma palavra u\in\Sigma^* via G, e a partir de cada ocorrência de S_a geramos em seguida uma palavra em s(a) usando produções de G_a. Assim obtemos um u\in L e uma escolha de w_i\in s(u_i) para cada símbolo u_i de u, de modo que a derivação monta exatamente w = w_1w_2\cdots w_{|u|}.
Logo w\in s(u)\subseteq s(L).

Passo 5

Mostramos s(L)\subseteq L(G_s). Seja w\in s(L). Então existe u=u_1u_2\cdots u_k\in L e, para cada i, uma palavra w_i\in s(u_i) tal que
w = w_1w_2\cdots w_k.
Como u\in L(G), há derivação
S\;\xLongrightarrow[G]{*}\;u_1u_2\cdots u_k.
Na gramática G_s, repetimos essa derivação trocando cada passo
A\to u_i
por
A\to S_{u_i},
usando as produções de tipo 1. Dessa forma obtemos
S\;\xLongrightarrow[G_s]{*}\;S_{u_1}S_{u_2}\cdots S_{u_k}.
Em seguida, para cada i, dentro do componente G_{u_i}\subseteq G_s temos
S_{u_i}\;\xLongrightarrow[G_{u_i}]{*}\;w_i,
pois G_{u_i} gera s(u_i). Concatenando essas derivações, obtemos
S\;\xLongrightarrow[G_s]{*}\;w_1w_2\cdots w_k \;=\;w,
logo w\in L(G_s).

Resposta

Com isso mostramos que L(G_s)=s(L) e que G_s é uma gramática livre de contexto. Portanto s(L) é de fato uma LLC.

Exercícios relacionados