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.