Exercício 13. Mostre que se L é LLC, então L^{R} (reverso) também é obs: Dê a construção a partir de uma GLC e depois tente provar formalmente.

Passo 1

O enunciado pede para mostrar que, se uma linguagem L\subseteq\Sigma^* é livre de contexto (LLC), então sua reversa
L^R = \{\,w^R \mid w\in L\}
também é LLC. O conteúdo que vamos usar é a construção de uma gramática livre de contexto que gera exatamente as palavras reversas, a partir de uma gramática para L, seguido de uma prova formal de que essa nova gramática gera L^R.

Passo 2

Seja
G = (V,\Sigma,P,S)
uma gramática livre de contexto que gera L, ou seja, L(G)=L. Definimos uma nova gramática
G^R = (V,\Sigma,P^R,S)
em que o conjunto de produções P^R é obtido “invertendo” cada corpo de produção de P. Formalmente, para cada regra
A \to X_1X_2\cdots X_n
em P, onde cada X_i\in V\cup\Sigma, incluímos em P^R a regra
A \to X_n X_{n-1}\cdots X_1.

Passo 3

Agora vamos provar que L(G^R)=L(G)^R. O ponto central é mostrar que, para toda variável A e toda cadeia \alpha\in(V\cup\Sigma)^*, vale
A \xRightarrow[G]{*} \alpha \quad\Longleftrightarrow\quad A \xRightarrow[G^R]{*} \alpha^R.
Fazemos isso por indução no número de etapas da derivação em G.
Base (0 etapas): Se A = \alpha e não há substituições, então \alpha é exatamente A e \alpha^R = A. Assim
A \xRightarrow[\,G\,]{0} A \quad\text{e}\quad A \xRightarrow[\,G^R\,]{0} A,
logo a equivalência vale trivialmente.
Passo indutivo: Suponha que toda derivação em até k passos satisfaz a equivalência. Considere uma derivação em k+1 passos
A \xRightarrow[\,G\,]{1} X_1\cdots X_n \xRightarrow[\,G\,]{k} \alpha,
onde a primeira aplicação usa a regra A\to X_1\cdots X_n em P, e nas k etapas seguintes chega-se a \alpha. Então \alpha se decompõe como concatenação de subcadeias \alpha_1\alpha_2\cdots\alpha_n, cada uma derivada de X_i em k_i passos, com k_1+\cdots+k_n = k. Por hipótese de indução, para cada i vale
X_i \xRightarrow[\,G^R\,]{*} \alpha_i^R.
Na gramática G^R aplicamos primeiro a regra invertida
A \to X_n\cdots X_1,
e em seguida derivamos cada X_i em \alpha_i^R. A ordem das deriv ações faz com que, ao final, obtenhamos
A \xRightarrow[\,G^R\,]{1} X_n\cdots X_1 \xRightarrow[\,G^R\,]{k} \alpha_n^R\cdots\alpha_1^R = \alpha^R.
Isso mostra o lado “ \Rightarrow”. O lado “ \Leftarrow” usa a mesma argumentação trocando papéis de G e G^R.

Passo 4

Da equivalência acima segue imediatamente que
L(G^R) = \{\,w \mid S\xRightarrow[G^R]{*} w\} = \{\,w \mid S\xRightarrow[G]{*} w^R\} = \{\,u^R \mid u\in L(G)\} = L(G)^R.
Portanto G^R é uma gramática livre de contexto que gera L^R.

Resposta

A construção de G^R inverte o corpo de cada produção de G, e a prova por indução sobre o número de etapas de derivação garante que L(G^R)=L(G)^R. Assim, L^R é LLC.

Exercícios relacionados