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 de compiladores, la noción se distingue de la equivalencia fuerte (o estructural ) , 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] demuestran que las gramáticas indexadas lineales , las gramáticas categóricas combinatorias , las gramáticas contiguas a árboles y las gramáticas principales son formalismos débilmente equivalentes, [ aclaración necesaria ] ya que todas definen los mismos lenguajes de cadenas.
Por otra parte, si dos gramáticas generan el mismo conjunto de árboles de derivación (o, de manera más general, 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 sostiene 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 equivalencia fuerte 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 que para cualquier formalismo LTAG , existe uno HPSG fuertemente equivalente .
Como ejemplo, considere las siguientes dos gramáticas libres de contexto , [nota 1] dadas en forma Backus-Naur :
< expresión > ::= < expresión > "+" < expresión > | < expresión > "-" < expresión > | < expresión > "*" < expresión > | < expresión > "/" < expresión > | "x" | "y" | "z" | "1" | "2" | "3" | "(" < expresión > ")"< expresión > ::= < término > | < expresión > "+" < término > | < expresión > "-" < término > < término > ::= < factor > | < término > "*" < factor > | < término > "/" < factor > < factor > ::= "x" | "y" | "z" | "1" | "2" | "3" | "(" < expresión > ")"Ambas gramáticas generan el mismo conjunto de cadenas, es decir, 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 los paréntesis "(" y ")". Sin embargo, un árbol sintáctico concreto de la segunda gramática siempre refleja el orden habitual de operaciones , mientras que un árbol de la primera gramática no necesita hacerlo.
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 posfijo dará como resultado el valor apropiado, 7. En contraste, la parte izquierda de la imagen muestra uno de los árboles de análisis 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 izquierda de la imagen, mientras que la primera gramática sí puede, ambas gramáticas no son fuertemente equivalentes.
En lingüística, la capacidad generativa débil de una gramática se define como el conjunto de todas las cadenas generadas por ella [nota 3], mientras que la capacidad generativa fuerte de una gramática se refiere al conjunto de "descripciones estructurales" [nota 4] generadas por ella [7] . En consecuencia, dos gramáticas se consideran débilmente equivalentes si sus capacidades generativas débiles coinciden; similares si son de equivalencia fuerte. La noción de capacidad generativa fue introducida por Noam Chomsky en 1963 [3] [7]
{{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )