Diferencia entre gramática ambigua y no ambigua

los diferencia principal Entre la gramática ambigua y no ambigua es que la la gramática ambigua es una gramática libre de contexto para la cual existe una cadena que puede tener más de una derivación a la izquierda mientras que una gramática no ambigua es una gramática libre de contexto para la cual cada cadena válida tiene una derivación única a la izquierda. 

Gramática se refiere a las reglas sintácticas en lenguajes naturales. En 1956, los científicos informáticos introdujeron un modelo matemático de gramática para escribir lenguaje informático. Si es posible derivar todas las cadenas de un lenguaje usando una gramática determinada, entonces se dice que el lenguaje se genera a partir de esa gramática. La gramática libre de contexto es un tipo de gramática. Esta gramática genera un contexto de lenguaje libre. La gramática libre de contexto puede ser ambigua o no ambigua. Para una cadena en particular, si hay dos o más derivaciones, se dice que la gramática es ambigua. Para una cadena en particular, si hay una única derivación más a la izquierda única, se dice que la gramática es una gramática inequívoca.

Áreas clave cubiertas

1. ¿Qué es la gramática ambigua?
     - Definición, ejemplo
2. ¿Qué es la gramática inequívoca?
     - Definición, ejemplo
3. Diferencia entre gramática ambigua y no ambigua
     - Comparación de diferencias clave

Términos clave

Gramática ambigua, gramática no ambigua

¿Qué es la gramática ambigua?

Se dice que una gramática es ambigua si existen dos o más derivaciones para una cadena.

Figura 1: Gramática ambigua

Supongamos que hay una gramática definida como sigue.

G = (S, a + b, +, *, P, S. Las reglas de producción son las siguientes. S -> S + S | S * S | a | b. Supongamos que es necesario generar el String a + a * b.

Considerar, S -> S + S

Sustituir 'a' por la izquierda más S dará lo siguiente.

S-> a + S

Sustituir S * S por S es como sigue.

S-> a + S * S 

Sustituyendo 'a' por la izquierda, más S dará la salida de abajo.

S -> a + a * S

Sustituir 'b' por la S dará el siguiente resultado.

S -> a + a * b

Esta es la cadena requerida para generar.

Al usar la otra regla de producción, dará

S -> S * S

Aplique S + S a la izquierda, más S dará lo siguiente.

S -> S + S * S

Sustituye 'a' por la izquierda más S,

S -> a + S * S

Sustituyendo 'a' por la izquierda más S,

S -> a + a * S

Sustituir 'b' por S dará el siguiente resultado.

S -> a + a * b

De nuevo, generó la cadena requerida. Por lo tanto, hay más de una derivación para generar la cadena. Por eso, es una gramática ambigua..

¿Qué es la gramática inequívoca?

En una gramática ambigua, una determinada cadena tiene una derivación única a la izquierda. Consulte las siguientes reglas de producción.

S -> L | a, L -> LS | S

Considere la regla S -> L Sustituir LS en lugar de L.

S -> LS

Sustituir S, por primera L.

S -> S S

Sustituir 'a' por la S más a la izquierda dará la siguiente salida.

S -> a S

Sustituir 'a' por S dará lo siguiente.

S -> a a

Por lo tanto, una cadena tiene una única derivación a la izquierda. Por lo tanto, es una gramática inequívoca..

Diferencia entre gramática ambigua y no ambigua

Definición

Una gramática ambigua es una gramática libre de contexto para la cual existe una cadena que puede tener más de una derivación a la izquierda o árboles de análisis. La gramática no ambigua es una gramática libre de contexto para la cual cada cadena válida tiene una derivación única a la izquierda o un árbol de análisis.

Número de derivaciones a la izquierda

En la gramática ambigua, una cadena puede tener dos o más derivaciones a la izquierda pero, en la gramática no ambigua, una cadena tiene una derivación única a la izquierda.

Conclusión

La gramática libre de contexto puede ser ambigua o no ambigua. La diferencia entre la gramática ambigua y no ambigua es que la gramática ambigua es una gramática libre de contexto para la cual existe una cadena que puede tener más de una derivación más a la izquierda mientras que una gramática no ambigua es una gramática libre de contexto para la cual cada cadena válida tiene una derivación única a la izquierda. 

Referencia:

1. “Gramática ambigua”. Wikipedia, Wikimedia Foundation, 17 de julio de 2018, disponible aquí.
2. “Diseño del compilador | Gramática ambigua. ”GeeksforGeeks, 10 de febrero de 2018, disponible aquí.
3. “Gramática ambigua”, Neso Academy, 29 de marzo de 2017, disponible aquí.

Imagen de cortesía:

1. "Leftmostderivations jaredwf" Por Jaredwf de Wikipedia en inglés - Transferido de en.wikipedia a Commons por EdwardHades (dominio público) a través de Commons Wikimedia