Encontre uma gramática de estrutura de frase que gere cada uma destas linguagens.
b) o conjunto das seqüências de bits com o dobro de 0 s do que de 1 s

Passo 1

O enunciado pede uma gramática livre de contexto que gere a linguagem L = \{\,w \in \{0,1\}^* \mid \#0(w) = 2\,\#1(w)\}.
Para resolver, vamos usar a ideia de blocos que contenham exatamente dois zeros e um um.

Passo 2

Como cada símbolo 1 deve “vir acompanhado” de dois zeros, podemos extrair dessa condição um bloco atômico que contenha exatamente dois zeros e um um, em qualquer ordem. Chamaremos esse bloco de T.

Passo 3

Primeiro, definimos as produções de T de forma a gerar todas as permutações de dois zeros e um um:
T \to 001 \mid 010 \mid 100
Em seguida, permitimos que o símbolo inicial S gere qualquer número (inclusive zero) desses blocos, garantindo assim que no total tenhamos duas zeros para cada um:
S \to T\,S \mid \epsilon

Resposta

S \to T\,S \mid \epsilon
T \to 001 \mid 010 \mid 100

Exercícios de Livros Relacionados