👉 Ambigüedad en gramáticas libres de contexto

Ambigüedad en gramáticas libres de contexto

Si gramática libre de contexto gramo tiene más de un árbol de salida para alguna línea w ∈ L (G), se llama gramática ambigua… Hay varias derivadas más a la derecha o más a la izquierda para algunas cadenas basadas en esta gramática.

Problema

Compruebe si la gramática G se ajusta a las reglas de producción –

X → X + X | X * X | X | y

ambiguo o no.

Decisión

Busquemos el árbol de origen de la cadena «a + a * a». Tiene dos pines más a la izquierda.

Conclusión 1 – X → X + X → a + X → a + X * X → a + a * X → a + a * a

Parse árbol 1 –

Conclusión 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 línea «a + a * a», la gramática gramo ambiguo.

Ambigüedad en gramáticas libres de contexto