Gramática ambigua
En Ciencias de la Computación, una gramática ambigua es un Gramática libre del contexto para la que existe una cadena que puede tener más de una derivación a la izquierda, mientras una gramática no ambigua es una Gramática libre del contexto para la que cada cadena válida tiene una única derivación a la izquierda.
El ejemplo más sencillo es la gramática ambigua siguiente para el lenguaje trivial, que consta sólo de la cadena vacía: …significando que una producción puede ser ella misma otra vez, o la cadena vacía.
De la misma manera, cualquier gramática para un lenguaje no vacío puede ser convertida a ambigua al añadir duplicados.
El lenguaje regular de cadenas unarias de un carácter dado, por ejemplo, 'a' (la expresión regular a*), tiene la gramática no-ambigua: …pero también tiene la gramática ambigua: Esto equivale a producir un árbol asociativo a la derecha (para la gramática no-ambigua) o dejando tanto la asociación izquierda como la derecha.
En el siguiente ejemplo, la gramática es ambigua dado que existen dos árboles de derivación para la cadena a + a − a El lenguaje que genera, aun así, no es inherentemente ambiguo; la siguiente es una gramática no-ambigua que genera el mismo lenguaje: El problema de decisión general de si una gramática es ambigua es no decidible y puede ser demostrado que es equivalente al problema de correspondencia de Post.
[1] Al menos, existen herramientas que implementan algún procedimiento de decisión para detectar ambigüedad de gramáticas libres del contexto.
Las gramáticas libres del contexto deterministas están aceptadas por autómatas con pila deterministas y pueden ser analizadas en tiempo lineal, por ejemplo por el Analizador sintáctico LR.
[3] Este es un subconjunto de las gramáticas libres del contexto que son aceptadas por el autómata con pila y pueden ser analizadas en tiempo polinómico, por ejemplo por el algoritmo CYK.
Las gramáticas libres del contexto no-ambiguas pueden ser no deterministas.
Una cadena arbitraria de este lenguaje no puede ser derivada sin leer todas sus letras primero, lo que significa que un autómata con pila tiene que probar transiciones de estado alternativas para acomodar las diferentes longitudes posibles de un cadena semi-analizada.
[4] Eliminar la ambigüedad de una gramática puede producir una gramática libre del contexto determinista y así permitir análisis más eficientes.
[5] Mientras algunos lenguajes libres del contexto (el conjunto de cadenas que puede ser generado por una gramática) tienen tanto gramáticas ambiguas como no-ambiguas, existen lenguajes libres del contexto para los que no existe una GLC no-ambigua.
Pero Hopcroft y Ullman (1979) brindaron una demostración de que no hay ninguna manera de analizar cadenas sintácticamente en forma no-ambigua en el subconjunto común
