Ambigüedad en gramáticas libres de contexto

Si una gramática libre de contexto G tiene más de un árbol de derivación para alguna cadena w ∈ L(G), se llama ambiguous grammar. Existen múltiples derivaciones más a la derecha o más a la izquierda para alguna cadena generada a partir de esa gramática.

Problema

Compruebe si la gramática G con reglas de producción -

X → X + X | X * X | X | una

es ambiguo o no.

Solución

Averigüemos el árbol de derivación de la cadena "a + a * a". Tiene dos derivaciones más a la izquierda.

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 -

Como hay dos árboles de análisis para una sola cadena "a + a * a", la gramática G es ambiguo.