O que é a linguagem gerada por uma gramática
com vocabulário
, conjunto de terminais
,
, símbolo inicial
e regras de produção
,
?
Passo 1
O enunciado nos dá uma gramática
com variáveis
, terminais
, símbolo inicial
e produções
Passo 2
Toda derivação de
deve, em algum momento, usar a produção
para terminar. Antes disso, podemos aplicar repetidamente
. Assim, o processo geral é:
onde
é 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
acrescenta exatamente três zeros ao início da cadeia. Quando a derivação termina com
, obtemos uma cadeia composta de
zeros seguida de um único
. Logo, todas as cadeias de
têm a forma
com
.