Encontre uma gramática de estrutura de frase que gere cada uma destas linguagens.
a) o conjunto das seqüências de bits da forma 0^{2 n} 1^{3 n}, em que n é um inteiro não negativo

Passo 1

O enunciado pede uma gramática livre de contexto (gramática de estrutura de frase) que gere a linguagem
L = \{\,0^{2n}1^{3n}\mid n\ge0\}.
O conteúdo aplicado aqui é o de gramáticas livres de contexto, em que usamos variáveis e produções para impor a relação exata entre o número de símbolos 0 e 1.

Passo 2

Para forçar a cada passo a geração de exatamente dois 0s e três 1s, usamos uma única variável de partida S e as seguintes produções:
S \to 00\,S\,111 S \to \varepsilon A produção S \to 00\,S\,111 adiciona dois 0s no início e três 1s no fim da cadeia gerada por S, e a produção S \to \varepsilon garante o caso base n=0.

Passo 3

Verificação informal:
  1. Para n=0, usamos diretamente S\to\varepsilon, gerando a cadeia vazia, que é 0^{2\cdot0}1^{3\cdot0}.
  2. Supondo que S gera 0^{2n}1^{3n}, então uma aplicação de S\to00\,S\,111 gera
00\,(0^{2n}1^{3n})\,111 = 0^{2(n+1)}1^{3(n+1)},
completando o passo indutivo.
Não há outra forma de gerar cadeias nessa gramática, logo ela gera exatamente L.

Resposta

A gramática que gera L=\{0^{2n}1^{3n}\mid n\ge0\} é dada por:
S \to 00\,S\,111 \;\mid\; \varepsilon.