Exercício 13. Mostre que se L é LLC, então
(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
é livre de contexto (LLC), então sua reversa
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
, seguido de uma prova formal de que essa nova gramática gera
.
Passo 2
Seja
uma gramática livre de contexto que gera
, ou seja,
. Definimos uma nova gramática
em que o conjunto de produções
é obtido “invertendo” cada corpo de produção de
. Formalmente, para cada regra
em
, onde cada
, incluímos em
a regra
Passo 3
Agora vamos provar que
. O ponto central é mostrar que, para toda variável
e toda cadeia
, vale
Fazemos isso por indução no número de etapas da derivação em
.
Base (0 etapas): Se
e não há substituições, então
é exatamente
e
. Assim
logo a equivalência vale trivialmente.
Passo indutivo: Suponha que toda derivação em até
passos satisfaz a equivalência. Considere uma derivação em
passos
onde a primeira aplicação usa a regra
em
, e nas
etapas seguintes chega-se a
. Então
se decompõe como concatenação de subcadeias
, cada uma derivada de
em
passos, com
. Por hipótese de indução, para cada
vale
Na gramática
aplicamos primeiro a regra invertida
e em seguida derivamos cada
em
. A ordem das deriv ações faz com que, ao final, obtenhamos
Isso mostra o lado “
”. O lado “
” usa a mesma argumentação trocando papéis de
e
.
Passo 4
Da equivalência acima segue imediatamente que
Portanto
é uma gramática livre de contexto que gera
.
Resposta
A construção de
inverte o corpo de cada produção de
, e a prova por indução sobre o número de etapas de derivação garante que
. Assim,
é LLC.