Qual linguagem é gerada pela gramática S \rightarrow a S a I bSb | \in ?
a) Palavras com número par de símbolos.
b) Palíndromos sobre \{\mathrm{a}, \mathrm{b}\}.
c) Linguagem vazia.
d) \left\{a^{n} b^{n} \mid n \geq 0\right\}.
e) Qualquer palavra sobre \{a, b\}.

Passo 1

O enunciado dá a gramática
S \;\rightarrow\; aSa \;\mid\; bSb \;\mid\;\epsilon
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 S\to\epsilon gera a palavra vazia, que é palíndroma.
  • Se S gera uma palavra w, então aplicando S\to aSa gera a\,w\,a. Como w é palíndromo, a\,w\,a também é palíndromo (simetricamente).
  • De modo análogo, S\to bSb leva w em b\,w\,b, que também é palíndromo.
    Logo, toda palavra em L(G) é um palíndromo sobre \{a,b\}.

Passo 3

Agora mostramos que toda palavra palíndroma sobre \{a,b\} pode ser gerada por essa gramática. Seja u um palíndromo.
  • Se u for a palavra vazia, usamos S\to\epsilon.
  • Caso contrário, u tem primeiro e último símbolo iguais, digamos ambos a (ou ambos b). Então u=a\,v\,a (ou u=b\,v\,b), onde v é um palíndromo menor. Por hipótese de indução, v é gerado por S. Basta aplicar a produção correspondente ( aSa ou bSb) para obter u.
    Assim, todo palíndromo é gerado.

Resposta

b) Palíndromos sobre \{a,b\}.

Exercícios relacionados