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
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
.
Para resolver, vamos usar a ideia de blocos que contenham exatamente dois zeros e um um.
Para resolver, vamos usar a ideia de blocos que contenham exatamente dois zeros e um um.
Passo 2
Como cada símbolo
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
.
Passo 3
Primeiro, definimos as produções de
de forma a gerar todas as permutações de dois zeros e um um:
Em seguida, permitimos que o símbolo inicial
gere qualquer número (inclusive zero) desses blocos, garantindo assim que no total tenhamos duas zeros para cada um: