Exercício 12. Prove que se
é uma LLC sobre alfabeto
e s é uma substituição de
tal que s(a) é uma
para todo a
, então
é uma
.
Obs: Primeiro descreva como constrir uma
para
e depois prove que
.
Obs: Primeiro descreva como constrir uma
Passo 1
O enunciado afirma que
é uma linguagem livre de contexto (LLC) gerada por alguma gramática
sobre o alfabeto
, e que temos uma substituição
tal que, para cada símbolo terminal
, a linguagem
também é uma LLC. Queremos mostrar que
é uma LLC. Para isso, primeiro vamos construir explicitamente uma gramática
que gere
, depois provamos que
.
Passo 2
Sejam
uma gramática livre de contexto com
, e, para cada
,
uma gramática livre de contexto com
. Aqui
é o alfabeto comum em que todas as
estão definidas (pode ser a união dos alfabetos de cada
).
Passo 3
Definimos a nova gramática
onde o conjunto de regras [P_s) é a união de duas partes:
- Para cada produção original
onde cada é ou um não-terminal de ou um terminal , incluímos em a produção em que - Todas as produções de cada (G_a], isto é,
O símbolo inicial de
permanece
.
Passo 4
Mostramos
. Seja
. Então existe derivação
Fazemos indução sobre o número de passagens em que aplicamos regras do tipo 1 (as que vêm de
).
- Base: se nenhuma regra do tipo 1 foi usada, a derivação ficou inteiramente dentro de algum
, mas não pode, pois não é não-terminal de nenhum . - Passo indutivo: na primeira vez que usamos uma produção de tipo 1, digamos
cujo trecho corresponde a uma produção original em . Até esse ponto a árvore de derivação corresponde a produzir alguma palavra via , e a partir de cada ocorrência de geramos em seguida uma palavra em usando produções de . Assim obtemos um e uma escolha de para cada símbolo de , de modo que a derivação monta exatamente
Logo
.
Passo 5
Mostramos
. Seja
. Então existe
e, para cada
, uma palavra
tal que
Como
, há derivação
Na gramática
, repetimos essa derivação trocando cada passo
por
usando as produções de tipo 1. Dessa forma obtemos
Em seguida, para cada
, dentro do componente
temos
pois
gera
. Concatenando essas derivações, obtemos
logo
.
Resposta
Com isso mostramos que
e que
é uma gramática livre de contexto. Portanto
é de fato uma LLC.