Dê uma gramática de estrutura de frase que gere 0 conjunto \left\{01^{n} \mid n=0,1,2, \ldots\right\}.

Passo 1

O enunciado pede uma gramática de estrutura de frase que gere a linguagem
L = \{\,0\,1^n \mid n=0,1,2,\ldots\}.
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 \Sigma = \{0,1\} (símbolos terminais), V = \{S, A\} (símbolos não-terminais),
símbolo inicial S.

Passo 3

Construímos as regras de produção P de forma que S produza o ‘0’ inicial e delegue a geração das ‘1’s ao não-terminal A. Escolhemos:
\begin{aligned} S &\to 0A,\\\ A &\to 1A,\\\ A &\to \varepsilon. \end{aligned}

Passo 4

Para gerar uma palavra da forma 0\,1^n, aplicamos primeiro
S \Rightarrow 0A,
depois repetimos A \Rightarrow 1A
exatamente n vezes e, por fim, encerramos com A \Rightarrow \varepsilon.
Assim obtemos todas as cadeias que começam em ‘0’ seguidas de n ocorrências de ‘1’.

Resposta

A gramática G=(V,\Sigma,P,S) que gera L é:
V = \{S,A\},\quad \Sigma = \{0,1\},
P = \bigl\{\,S \to 0A,\;A \to 1A,\;A \to \varepsilon\,\bigr\},
símbolo inicial S.

Exercícios de Livros Relacionados