Mostre que a gramática G=(V, T, S, P) \operatorname{com} V=\{0, S\}, T=\{0\}, estado inicial S e regras de produção S \rightarrow 0 S e S\rightarrow 0 não é ambígua.
Passo 1
O enunciado pede para mostrar que a gramática
G = (V, T, S, P)
com
V = \{S\},\quad T = \{0\},
e regras de produção
S \to 0S \quad\text{e}\quad S \to 0
não é ambígua.
Conteúdo: ambiguidade em gramáticas livres de contexto. Vamos provar que cada cadeia de zeros tem exatamente uma árvore de derivação em G.
Passo 2
Primeiro, observamos que G gera exatamente a linguagem
L(G) = \{0^n \mid n \ge 1\}.
De fato:
Para n=1, fazemos S \Rightarrow 0.
Para n>1, aplicamos S \Rightarrow 0S repetidamente n-1 vezes e, por fim, em
S \;\Rightarrow\; \underbrace{0S}_{n-1\text{ vezes}}\;\Rightarrow\;0\underbrace{0}_{n-1} = 0^n.
Passo 3
Vamos provar por indução em n que toda cadeia 0^n tem exatamente uma árvore de derivação.
Base n=1:
Só há um modo de derivar 0, pois a única produção que gera uma cadeia de comprimento 1 é
S \;\Rightarrow\; 0.
Logo há exatamente uma árvore de derivação.
Passo indutivo:
Suponha que para algum k\ge1 a cadeia 0^k tenha exatamente uma árvore de derivação. Considere agora 0^{k+1}. Qualquer derivação de 0^{k+1} em G deve começar por
S \;\Rightarrow\; 0S,
pois a produção S\to0 gera apenas um símbolo terminal. Após esse primeiro passo, resta derivar 0^k a partir do não-terminal final S. Por hipótese indutiva, há exatamente uma derivação (e árvore) de S para 0^k. Consequentemente, há exatamente uma árvore de derivação de S para 0^{k+1}.
Passo 4
Concluímos que, para todo n\ge1, a cadeia 0^n tem uma e somente uma árvore de derivação em G. Isso significa que G não é ambígua.
Resposta
A gramática G não é ambígua.
Cálculo - Kenneth Rosen - Matemática Discreta e suas Aplicações - 6ª Edição - Capítulo 12.Exercícios Complementares - Ex. 6