Ambiguidade em gramáticas livres de contexto

Se uma gramática livre de contexto G tem mais de uma árvore de derivação para alguma string w ∈ L(G), é chamado de ambiguous grammar. Existem várias derivações mais à direita ou mais à esquerda para alguma string gerada a partir dessa gramática.

Problema

Verifique se a gramática G com regras de produção -

X → X + X | X * X | X | uma

é ambíguo ou não.

Solução

Vamos descobrir a árvore de derivação para a string "a + a * a". Possui duas derivações mais à esquerda.

Derivation 1- X → X + X → a + X → a + X * X → a + a * X → a + a * a

Parse tree 1 -

Derivation 2- X → X * X → X + X * X → a + X * X → a + a * X → a + a * a

Parse tree 2 -

Uma vez que existem duas árvores de análise para uma única string "a + a * a", a gramática G é ambíguo.