Questão 3 - (8 pontos) - Dada a gramática:
S a lambda lambda
A A 14 / b B
B b R 1 S
C c C l c
A) Mostre a linguagem gerada pela gramática. (2 pontos)

Passo 1

Beleza, vamos lá! A gente tem uma gramática com várias regras e precisa descobrir qual linguagem (ou seja, quais palavras) ela gera. Isso está dentro do conteúdo de Gramáticas e Linguagens Formais. Pra resolver isso, vamos usar as regras de produção da gramática e ver como combinamos os símbolos para formar palavras válidas.

Passo 2

Primeiro, vamos olhar cada regra da gramática:
  • $ S \rightarrow a \lambda \lambda $
  • $ A \rightarrow A , 14 , / , b , B $
  • $ B \rightarrow b , R , 1 , S $
  • $ C \rightarrow c , C , l , c $
Aqui, $ \lambda $ representa a string vazia, ou seja, nada.

Passo 3

Começando pela regra $ S \rightarrow a \lambda \lambda $, isso significa que o símbolo $ S $ pode ser substituído por “a” seguido de duas strings vazias. Como strings vazias não adicionam nada, simplificamos para:
S a lambda lambda
Então, a única palavra que $ S $ gera diretamente é “a”.

Passo 4

Vamos ver as outras regras para ver se podemos gerar mais palavras. Observando a regra de $ A $:
A
Isso significa que $ A $ pode ser substituído por $ A , 14 $ ou por $ b , B $. Mas se a gente tentar seguir substituindo $ A $, acabamos numa cadeia infinita porque $ A $ pode continuamente se expandir para $ A , 14 $.

Passo 5

Agora, olhando para a regra de $ B $:
B
Sabemos que $ S $ gera “a”. Então substituindo:
B b , R , 1 , S
Isso nos dá a palavra “bR1a”.

Passo 6

Voltando na regra de $ A $, se escolhermos a produção $ b , B $:
A
Isso resulta na palavra “bbR1a”.

Passo 7

Por fim, vamos ver a regra de $ C $:
C
Aqui, $ C $ pode ser substituído por $ c , C , l , c $, e isso também gera uma sequência infinita de “c” e “l”. Porém, como não conseguimos finalizar essa substituição sem um caso base, a regra de $ C $ não gera palavras terminadas, então vamos focar nas regras que realmente geram palavras finitas.

Resposta

A linguagem gerada pela gramática é o conjunto das palavras que começam com “a” ou com uma sequência de “b” seguida de “R1a”. Ou seja,
L = a, bR1a, bbR1a, bbbR1a, dots

Exercícios relacionados