Encontre uma gramática de estrutura de frase que gere cada uma destas linguagens.
a) o conjunto das seqüências de bits da forma
, em que
é um inteiro não negativo
a) o conjunto das seqüências de bits da forma
Passo 1
O enunciado pede uma gramática livre de contexto (gramática de estrutura de frase) que gere a linguagem
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
e
.
Passo 2
Para forçar a cada passo a geração de exatamente dois
s e três
s, usamos uma única variável de partida
e as seguintes produções:
Passo 3
Verificação informal:
- Para
, usamos diretamente , gerando a cadeia vazia, que é . - Supondo que
gera , então uma aplicação de gera
completando o passo indutivo.
Não há outra forma de gerar cadeias nessa gramática, logo ela gera exatamente .
Não há outra forma de gerar cadeias nessa gramática, logo ela gera exatamente
Resposta
A gramática que gera
é dada por: