Equivalencia (lenguajes formales)
En la teoría del lenguaje formal , la equivalencia débil de dos gramáticas significa que generan el mismo conjunto de cadenas, es decir, que el lenguaje formal que generan es el mismo. En la teoría del compilador, la noción se distingue de la equivalencia fuerte (o estructural ) , lo que además significa que los dos árboles de análisis sintáctico [ aclaración necesaria ] son razonablemente similares en el sentido de que se puede asignar la misma interpretación semántica a ambos. [1]
Vijay-Shanker y Weir (1994) [2] demuestra que Lineal indexado gramáticas , Combinatoria categorial gramáticas , gramáticas Árbol-contigua , y la cabeza gramáticas son débilmente formalismos equivalentes, [ clarifique ] en la que todos ellos definen los mismos idiomas de cuerda.
Por otro lado, si dos gramáticas generan el mismo conjunto de árboles de derivación (o más generalmente, el mismo conjunto de objetos sintácticos abstractos), entonces las dos gramáticas son fuertemente equivalentes. Chomsky (1963) [3] introduce la noción de equivalencia fuerte y argumenta que solo la equivalencia fuerte es relevante cuando se comparan formalismos gramaticales. Kornai y Pullum (1990) [4] y Miller (1994) [5] ofrecen una noción refinada de fuerte equivalencia que permite relaciones isomórficas entre los análisis sintácticos dados por diferentes formalismos. Yoshinaga, Miyao y Tsujii (2002) [6] ofrecen una prueba de la fuerte equivalencia de los formalismos LTAG y HPSG .
Ambas gramáticas generan el mismo conjunto de cadenas, a saber. el conjunto de todas las expresiones aritméticas que se pueden construir a partir de las variables "x", "y", "z", las constantes "1", "2", "3", los operadores "+", "-", " * "," / "y paréntesis" ("y") ". Sin embargo, un árbol de sintaxis concreto de la segunda gramática siempre refleja el orden habitual de operaciones , mientras que un árbol de la primera gramática no es necesario.
Para la cadena de ejemplo "1 + 2 * 3", la parte derecha de la imagen muestra su árbol de análisis único con la segunda gramática; [nota 2] evaluar este árbol en orden de sufijo producirá el valor adecuado, 7. En contraste, la parte de la imagen de la izquierda muestra uno de los árboles de análisis sintáctico para esa cadena con la primera gramática; evaluarlo en orden posfijo dará como resultado 9.
Dado que la segunda gramática no puede generar un árbol correspondiente a la parte de la imagen izquierda, mientras que la primera gramática sí puede, ambas gramáticas no son fuertemente equivalentes.
