Ambiguità nelle grammatiche libere dal contesto

Se una grammatica libera dal contesto G ha più di un albero di derivazione per qualche stringa w ∈ L(G), si chiama un ambiguous grammar. Esistono più derivazioni più a destra o più a sinistra per alcune stringhe generate da quella grammatica.

Problema

Controlla se la grammatica G con le regole di produzione -

X → X + X | X * X | X | un

è ambiguo o no.

Soluzione

Scopriamo l'albero di derivazione per la stringa "a + a * a". Ha due derivazioni più a sinistra.

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 -

Poiché ci sono due alberi di analisi per una singola stringa "a + a * a", la grammatica G è ambiguo.