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 .
Ejemplo de gramática sin contexto
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, 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 postfijo 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.
Capacidad generativa
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] Como consecuencia, dos gramáticas se consideran débilmente equivalentes si sus débiles capacidades generativas coinciden; similar para una fuerte equivalencia. La noción de capacidad generativa fue introducida por Noam Chomsky en 1963. [3] [7]
Notas
- ^ con el símbolo de inicio "
" ón> - ^ usando las abreviaturas "E", "T" y "F" para
, ón>y érmino>, respectivamente - ^ para gramáticas libres de contexto: vea Gramática libre de contexto # Lenguaje libre de contexto para una definición formal
- ^ para gramáticas libres de contexto: árboles de sintaxis concretos
Referencias
- ^ Stefano Crespi Reghizzi (2009). Lenguajes formales y compilación . Saltador. pag. 57. ISBN 978-1-84882-049-4.
- ^ Vijay-Shanker, K. y Weir, David J. (1994). "La equivalencia de cuatro extensiones de gramáticas libres de contexto" . Teoría de sistemas matemáticos . 27 (6): 511–546.CS1 maint: varios nombres: lista de autores ( enlace )
- ^ a b Noam Chomsky (1963). "Propiedades formales de la gramática". En RD Luce; RR Bush; E. Galanter (eds.). Manual de Psicología Matemática . II . Nueva York: Wiley. págs. 323 —418.
- ^ Kornai, A. y Pullum, GK 1990. La teoría de la estructura de la frase X-bar . Idioma, 66: 24-50.
- ^ Miller, Philip H. 1999. Fuerte capacidad generativa . Publicaciones CSLI.
- ^ "Yoshinaga, N., Miyao Y. y Tsujii, J. 2002. Una prueba formal de fuerte equivalencia para una conversión gramatical del estilo LTAG al HPSG . En las Actas del Taller TAG + 6: 187-192. Venecia, Italia " (PDF) . Archivado desde el original (PDF) el 28 de agosto de 2011 . Consultado el 5 de febrero de 2012 .
- ^ a b Emmon Bach; Philip Miller (2003). "Capacidad Generativa" (PDF) . En William J. Frawley (ed.). Enciclopedia Internacional de Lingüística (2ª ed.). Prensa de la Universidad de Oxford. doi : 10.1093 / acref / 9780195139778.001.0001 . ISBN 9780195139778.