Qual linguagem é gerada pela gramática
bSb |
?
a) Palavras com número par de símbolos.
b) Palíndromos sobre
.
c) Linguagem vazia.
d)
.
e) Qualquer palavra sobre
.
a) Palavras com número par de símbolos.
b) Palíndromos sobre
c) Linguagem vazia.
d)
e) Qualquer palavra sobre
Passo 1
O enunciado dá a gramática
e pede que identifiquemos qual linguagem essa gramática gera. O conteúdo envolvido é teoria de linguagens livres de contexto, especificamente a geração de palíndromos.
Passo 2
Mostramos primeiro que toda palavra gerada por essa gramática é um palíndromo.
- A produção
gera a palavra vazia, que é palíndroma. - Se
gera uma palavra , então aplicando gera . Como é palíndromo, também é palíndromo (simetricamente). - De modo análogo,
leva em , que também é palíndromo.
Logo, toda palavra emé um palíndromo sobre .
Passo 3
Agora mostramos que toda palavra palíndroma sobre
pode ser gerada por essa gramática. Seja
um palíndromo.
- Se
for a palavra vazia, usamos . - Caso contrário,
tem primeiro e último símbolo iguais, digamos ambos (ou ambos ). Então (ou ), onde é um palíndromo menor. Por hipótese de indução, é gerado por . Basta aplicar a produção correspondente ( ou ) para obter .
Assim, todo palíndromo é gerado.
Resposta
b) Palíndromos sobre
.