Mostre que a gramática
com
,
, estado inicial
e regras de produção
e
é ambígua, construindo duas árvores de derivação diferentes para
.
Passo 1
O enunciado pede para mostrar que a gramática
é ambígua, isto é, que existe uma mesma cadeia com duas árvores de derivação distintas. Vamos tomar a cadeia
e construir duas árvores diferentes.
Passo 2
Primeira derivação: usamos sempre a regra
até gerar três zeros e então fechamos com
.
A árvore de derivação em notação entre colchetes fica:
Passo 3
Segunda derivação: agora usamos sempre a regra
até obter três zeros e então fechamos com
.
A árvore de derivação correspondente é:
Passo 4
Como
e
têm estruturas diferentes mas geram a mesma cadeia
, a gramática é ambígua.
Resposta
As duas árvores de derivação para
são