O que é a linguagem gerada por uma gramática G com vocabulário {S, 0,1}, conjunto de terminais T=\{0, 1\}, símbolo inicial S e regras de produção S \rightarrow 000 S, S \rightarrow 1 ?

Passo 1

O enunciado nos dá uma gramática G com variáveis \{S\}, terminais \{0,1\}, símbolo inicial S e produções
S \rightarrow 000\,S S \rightarrow 1. O objetivo é determinar a forma geral das cadeias geradas por G.

Passo 2

Toda derivação de S deve, em algum momento, usar a produção S \rightarrow 1 para terminar. Antes disso, podemos aplicar repetidamente S \rightarrow 000\,S. Assim, o processo geral é:
S \;\Rightarrow\; 000\,S \;\Rightarrow\; 000\;000\,S \;\Rightarrow\;\cdots\; \Rightarrow\; 000^{k}\,S \;\Rightarrow\; 000^{k}\,1,
onde k\ge0 é o número de vezes que escolhemos a produção que adiciona “000” antes de finalmente substituir por “1”.

Passo 3

Cada aplicação de S\rightarrow 000\,S acrescenta exatamente três zeros ao início da cadeia. Quando a derivação termina com S\rightarrow 1, obtemos uma cadeia composta de 3k zeros seguida de um único 1. Logo, todas as cadeias de L(G) têm a forma
0^{3k}1,
com k\ge0.

Resposta

L(G) \;=\;\{\,0^{3k}1 \mid k\ge0\,\}.

Exercícios de Livros Relacionados