Dê uma gramática de estrutura de frase que gere 0 conjunto
.
Passo 1
O enunciado pede uma gramática de estrutura de frase que gere a linguagem
O conteúdo é teoria de linguagens formais e gramáticas, e a estratégia é escolher não-terminais que produzam o ‘0’ inicial e depois gerem arbitrariamente ‘1’s.
Passo 2
Definimos
(símbolos terminais),
(símbolos não-terminais),
símbolo inicial .
símbolo inicial
Passo 3
Construímos as regras de produção
de forma que
produza o ‘0’ inicial e delegue a geração das ‘1’s ao não-terminal
. Escolhemos:
Passo 4
Para gerar uma palavra da forma
, aplicamos primeiro
depois repetimos
exatamente vezes e, por fim, encerramos com
Assim obtemos todas as cadeias que começam em ‘0’ seguidas de ocorrências de ‘1’.
exatamente
Assim obtemos todas as cadeias que começam em ‘0’ seguidas de
Resposta
A gramática
que gera
é:
símbolo inicial
.