Mostre que a gramática G=(V, T, S, P) com V=\{0, S\}, T=\{0\}, estado inicial S e regras de produção S \rightarrow 0 S, S \rightarrow S 0 e S \rightarrow 0 é ambígua, construindo duas árvores de derivação diferentes para 0^{3}.

Passo 1

O enunciado pede para mostrar que a gramática
G=(\{0,S\},\{0\},S,\{\,S\to 0S,\;S\to S0,\;S\to 0\})
é ambígua, isto é, que existe uma mesma cadeia com duas árvores de derivação distintas. Vamos tomar a cadeia 000 e construir duas árvores diferentes.

Passo 2

Primeira derivação: usamos sempre a regra S\to 0S até gerar três zeros e então fechamos com S\to 0.
S\;\Rightarrow\;0S\;\Rightarrow\;00S\;\Rightarrow\;000
A árvore de derivação em notação entre colchetes fica:
T_1 = [\,S\;0\;[\,S\;0\;[\,S\;0]\,]\,].

Passo 3

Segunda derivação: agora usamos sempre a regra S\to S0 até obter três zeros e então fechamos com S\to 0.
S\;\Rightarrow\;S0\;\Rightarrow\;S00\;\Rightarrow\;000
A árvore de derivação correspondente é:
T_2 = [\,S\;[\,S\;[\,S\;0]\,0]\,0].

Passo 4

Como T_1 e T_2 têm estruturas diferentes mas geram a mesma cadeia 000, a gramática é ambígua.

Resposta

As duas árvores de derivação para 000 são
T_1 = [\,S\;0\;[\,S\;0\;[\,S\;0]\,]\,] \quad\text{e}\quad T_2 = [\,S\;[\,S\;[\,S\;0]\,0]\,0].

Exercícios de Livros Relacionados