Hispanopedia WikiEn lingüística computacional , el término formalismos gramaticales ligeramente sensibles al contexto se refiere a varios formalismos gramaticales que se han desarrollado en un esfuerzo por proporcionar descripciones adecuadas de la estructura sintáctica del lenguaje natural .
Todo formalismo gramatical ligeramente sensible al contexto define una clase de gramáticas ligeramente sensibles al contexto (las gramáticas que se pueden especificar en el formalismo) y, por lo tanto, también una clase de lenguajes ligeramente sensibles al contexto (los lenguajes formales generados por las gramáticas).
Fondo
Para 1985, varios investigadores en lingüística descriptiva y matemática habían aportado pruebas en contra de la hipótesis de que la estructura sintáctica del lenguaje natural puede describirse adecuadamente mediante gramáticas libres de contexto . [ 1 ] [ 2 ] Al mismo tiempo, el paso al siguiente nivel de la jerarquía de Chomsky , a las gramáticas sensibles al contexto , parecía innecesario e indeseable. En un intento por determinar el poder formal exacto requerido para la descripción adecuada de la sintaxis del lenguaje natural, Aravind Joshi caracterizó las "gramáticas (y lenguajes asociados ) que son solo ligeramente más potentes que las gramáticas libres de contexto (lenguajes libres de contexto)". [ 3 ] Llamó a estas gramáticas gramáticas ligeramente sensibles al contexto y a los lenguajes asociados lenguajes ligeramente sensibles al contexto .
La caracterización que Joshi hizo de las gramáticas ligeramente sensibles al contexto estaba sesgada hacia su trabajo sobre la gramática de adjunción de árboles (TAG). Sin embargo, junto con sus estudiantes Vijay Shanker y David Weir, Joshi pronto descubrió que las TAG son equivalentes, en términos de los lenguajes de cadenas generados, a la gramática de cabeza (HG) introducida independientemente. [ 4 ] A esto le siguieron dos resultados de equivalencia similares, para la gramática indexada lineal (LIG) [ 5 ] y la gramática categorial combinatoria (CCG), [ 6 ] que demostraron que la noción de sensibilidad al contexto leve es muy general y no está ligada a un formalismo específico.
Los formalismos equivalentes a TAG se generalizaron con la introducción de los sistemas de reescritura lineales libres de contexto (LCFRS). [ 7 ] [ 8 ] Estas gramáticas definen una jerarquía infinita de lenguajes de cadenas entre los lenguajes libres de contexto y los sensibles al contexto, con los lenguajes generados por los formalismos equivalentes a TAG en el extremo inferior de la jerarquía. De forma independiente y casi simultánea a LCFRS, Hiroyuki Seki et al. propusieron el formalismo esencialmente idéntico de gramática libre de contexto múltiple (MCFG). [ 9 ] LCFRS/MCFG se considera a veces el formalismo más general para especificar gramáticas ligeramente sensibles al contexto. Sin embargo, varios autores han señalado que algunas de las propiedades características de los formalismos equivalentes a TAG no se conservan en LCFRS/MCFG, [ 10 ] y que existen lenguajes que tienen las propiedades características de sensibilidad al contexto leve pero que no son generados por LCFRS/MCFG. [ 11 ]
En los últimos años se ha observado un mayor interés en la clase restringida de sistemas de reescritura libres de contexto lineales bien anidados /gramáticas libres de contexto múltiples, [ 10 ] [ 12 ] que definen una clase de gramáticas que incluye adecuadamente los formalismos equivalentes a TAG pero que está adecuadamente incluida en la jerarquía no restringida LCFRS/MCFG.
Caracterización
A pesar de la considerable cantidad de trabajo realizado sobre el tema, no existe una definición formal generalmente aceptada de sensibilidad al contexto leve.
Según la caracterización original de Joshi, [ 3 ] una clase de gramáticas ligeramente sensibles al contexto debería tener las siguientes propiedades:
- dependencias cruzadas seriales limitadas
- crecimiento constante
- análisis polinomial
Además de esto, se entiende que toda clase de gramáticas ligeramente sensibles al contexto debería ser capaz de generar todos los lenguajes libres de contexto.
La caracterización de Joshi no es una definición formal. Él señala: [ 3 ]
Esta es solo una caracterización aproximada, ya que las condiciones 1 y 3 dependen de las gramáticas, mientras que la condición 2 depende de los idiomas; además, la condición 1 debe especificarse con mucha más precisión de la que lo he hecho hasta ahora.
Otros autores han propuesto caracterizaciones alternativas de la sensibilidad al contexto leve, algunas de las cuales adoptan la forma de definiciones formales. Por ejemplo, Laura Kallmeyer [ 13 ] sostiene que la sensibilidad al contexto leve debería definirse como una propiedad de las clases de lenguas, en lugar de, como en la caracterización de Joshi, como una propiedad de las clases de gramáticas. Esta definición basada en el lenguaje conduce a una noción del concepto diferente a la de Joshi.
Dependencias entre series
El término dependencias seriales cruzadas se refiere a ciertos patrones característicos de ordenación de palabras, en particular a los patrones verbo-argumento observados en las oraciones subordinadas en neerlandés [ 1 ] y alemán suizo. [ 2 ] Estos son precisamente los patrones que pueden usarse para argumentar en contra de la independencia del contexto del lenguaje natural; por lo tanto, requerir gramáticas ligeramente sensibles al contexto para modelar las dependencias seriales cruzadas significa que estas gramáticas deben ser más potentes que las gramáticas libres de contexto.
Kallmeyer [ 13 ] identifica la capacidad de modelar dependencias seriales cruzadas con la capacidad de generar el lenguaje de copia.
y sus generalizaciones a dos o más copias de w , hasta cierto límite. Estos lenguajes no son libres de contexto, lo cual se puede demostrar utilizando el lema de bombeo .
Crecimiento constante
Un lenguaje formal es de crecimiento constante si cada cadena en dicho lenguaje es más larga que las siguientes cadenas más cortas por, como máximo, una constante (específica del lenguaje). Los lenguajes que violan esta propiedad suelen considerarse fuera del alcance de la capacidad humana, aunque algunos autores han argumentado que ciertos fenómenos del lenguaje natural sí muestran un crecimiento que no puede ser limitado por una constante. [ 14 ]
La mayoría de los formalismos gramaticales ligeramente sensibles al contexto (en particular, LCFRS/MCFG) satisfacen en realidad una propiedad más fuerte que el crecimiento constante llamada semilinealidad . [ 7 ] Un lenguaje es semilineal si su imagen bajo el mapeo de Parikh (el mapeo que "olvida" la posición relativa de los símbolos en una cadena, tratándola efectivamente como una bolsa de palabras) es un lenguaje regular . Todos los lenguajes semilineales son de crecimiento constante, pero no todo lenguaje con crecimiento constante es semilineal. [ 11 ]
Análisis polinomial
Se dice que un formalismo gramatical tiene análisis sintáctico polinomial si su problema de pertenencia puede resolverse en tiempo polinomial determinista . Este es el problema de decidir, dada una gramática G escrita en el formalismo y una cadena w , si w es generada por G , es decir, si w es "gramatical" según G. La complejidad temporal de este problema se mide en términos del tamaño combinado de G y w .
Desde la perspectiva de la sensibilidad al contexto leve como propiedad de las clases de lenguajes, el análisis sintáctico polinomial se refiere al problema de pertenencia a un lenguaje. Este problema consiste en decidir, para un lenguaje fijo L , si una cadena w dada pertenece a L. La complejidad temporal de este problema se mide en función de la longitud de w ; no tiene en cuenta cómo se especifica L.
Cabe señalar que ambas concepciones del análisis polinomial son idealizaciones, en el sentido de que, para aplicaciones prácticas, no solo interesa la cuestión de si una oración es gramatical o no, sino también la estructura sintáctica que la gramática le asigna.
Formalismos
A lo largo de los años, se han introducido numerosos formalismos gramaticales que satisfacen algunas o todas las propiedades características propuestas por Joshi. Varios de ellos cuentan con caracterizaciones alternativas basadas en autómatas que no se abordan en este artículo; por ejemplo, los lenguajes generados por la gramática de adjunción de árboles pueden caracterizarse mediante autómatas de pila incrustados .
Formalismos equivalentes a TAG
- Gramática de adjunción de árboles (TAG) [ 3 ]
- Gramática de cabeza (HG) [ 15 ] [ 16 ]
- Gramática indexada lineal (LIG) [ 17 ]
- Gramática categorial combinatoria (GCC) [ 6 ]
- LCFRS/MCFG bien anidado de fan-out 2
Formalismos equivalentes a LCFRS/MCFG generales
- Sistemas de reescritura lineales libres de contexto (LCFRS) [ 7 ] [ 8 ]
- Gramáticas libres de contexto múltiples (MCFG) [ 9 ]
- Gramáticas de adjunción de árboles multicomponente (MCTAG) [ 7 ]
- Gramáticas minimalistas (GM) [ 18 ]
- Gramáticas de concatenación de rango positivo simples (lineales, sin borrado, no combinatorias) (sRCG) [ 19 ]
Formalismos equivalentes a LCFRS/MCFG bien anidados
Relaciones entre los formalismos
Los sistemas de reescritura libres de contexto lineales/múltiples gramáticas libres de contexto forman una jerarquía bidimensional de poder generativo con respecto a dos parámetros específicos de la gramática llamados fan-out y rango . [ 22 ] Más precisamente, los lenguajes generados por LCFRS/MCFG con fan-out f ≥ 1 y rango r ≥ 3 están correctamente incluidos en la clase de lenguajes generados por LCFRS/MCFG con rango r + 1 y fan-out f , así como en la clase de lenguajes generados por LCFRS/MCFG con rango r y fan-out f + 1. En presencia de anidamiento adecuado, esta jerarquía colapsa a una jerarquía unidimensional con respecto a fan-out; Esto se debe a que cada LCFRS/MCFG bien anidado puede transformarse en un LCFRS/MCFG bien anidado equivalente con el mismo fan-out y rango 2. [ 10 ] [ 12 ] Dentro de la jerarquía LCFRS/MCFG, los lenguajes libres de contexto pueden caracterizarse por las gramáticas con fan-out 1; para este fan-out no hay diferencia entre gramáticas generales y bien anidadas. Los formalismos equivalentes a TAG pueden caracterizarse como LCFRS/MCFG bien anidados de fan-out 2.
Véase también
Referencias
- ^ Riny Huybregts. "La débil insuficiencia de las gramáticas de estructura de frases libres de contexto". En Ger de Haan, Mieke Trommelen y Wim Zonneveld, editores, Van periferie naar kern , páginas 81–99. Foris, Dordrecht, Países Bajos, 1984.
- 1 2 Stuart M. Shieber. " Evidencia en contra de la independencia de contexto del lenguaje natural ". Lingüística y filosofía , 8(3):333–343, 1985.
- 1 2 3 4 Aravind K. Joshi. " Gramáticas de adjunción de árboles: ¿Cuánta sensibilidad al contexto se requiere para proporcionar descripciones estructurales razonables? ". En David R. Dowty, Lauri Karttunen y Arnold M. Zwicky, editores, Análisis sintáctico del lenguaje natural , páginas 206-250. Cambridge University Press, 1985.
- ↑ David J. Weir, K. Vijay-Shanker y Aravind K. Joshi. « La relación entre las gramáticas de adjunción de árboles y las gramáticas de cabeza ». En Actas de la 24.ª Reunión Anual de la Asociación de Lingüística Computacional (ACL) , páginas 67-74, Nueva York, EE. UU., 1986.
- ↑ K. Vijay-Shanker. " Un estudio de las gramáticas de adjunción de árboles ". Tesis doctoral, Universidad de Pensilvania, Filadelfia, EE. UU., 1987.
- 1 2 David J. Weir y Aravind K. Joshi. " Gramáticas categóricas combinatorias: poder generativo y relación con los sistemas de reescritura lineales libres de contexto ". En Actas de la 26.ª Reunión Anual de la Asociación de Lingüística Computacional (ACL) , páginas 278-285, Buffalo, EE. UU., 1988.
- 1 2 3 4 K. Vijay-Shanker, David J. Weir y Aravind K. Joshi. " Caracterización de descripciones estructurales producidas por diversos formalismos gramaticales ". En Actas de la 25.ª Reunión Anual de la Asociación de Lingüística Computacional (ACL) , páginas 104-111, Stanford, CA, EE. UU., 1987.
- 1 2 David J. Weir. " Caracterización de formalismos gramaticales ligeramente sensibles al contexto ". Tesis doctoral, Universidad de Pensilvania, Filadelfia, EE. UU., 1988.
- 1 2 Hiroyuki Seki, Takashi Matsumura, Mamoru Fujii y Tadao Kasami. " Sobre múltiples gramáticas libres de contexto ". Theoretical Computer Science , 88(2):191–229, 1991.
- 1 2 3 4 Makoto Kanazawa. " El lema de bombeo para lenguajes libres de contexto múltiples bien anidados ". En Desarrollos en teoría del lenguaje. XIII Conferencia Internacional, DLT 2009, Stuttgart, Alemania, 30 de junio - 3 de julio de 2009. Actas , volumen 5583 de Lecture Notes in Computer Science , páginas 312-325, 2009.
- 1 2 Laura Kallmeyer. " Sobre la reescritura no lineal ligeramente sensible al contexto ". Investigación sobre lenguaje y computación , 8(4):341–363, 2010.
- 1 2 3 Carlos Gómez-Rodríguez, Marco Kuhlmann y Giorgio Satta. « Análisis sintáctico eficiente de sistemas de reescritura libres de contexto lineales bien anidados ». En Actas de Human Language Technologies: Conferencia anual de 2010 del capítulo norteamericano de la Asociación de Lingüística Computacional (NAACL) , páginas 276-284, Los Ángeles, EE. UU., 2010.
- 1 2 Laura Kallmeyer. Análisis sintáctico más allá de las gramáticas libres de contexto . Springer, 2010.
- ↑ Jens Michaelis y Marcus Kracht. « La semilinealidad como invariante sintáctico ». En Aspectos lógicos de la lingüística computacional. Primera Conferencia Internacional, LACL 1996, Nancy, Francia, 23-25 de septiembre de 1996. Artículos seleccionados , volumen 1328 de Lecture Notes in Computer Science , páginas 329-345. Springer, 1997.
- ↑ Carl J. Pollard . "Gramáticas generalizadas de estructura sintagmática, gramáticas de núcleo y lenguaje natural". Tesis doctoral, Universidad de Stanford, 1984.
- ↑ Kelly Roach. " Propiedades formales de las gramáticas de cabeza ". En Alexis Manaster-Ramer, editora, Matemáticas del lenguaje , páginas 293–347. John Benjamins, 1987.
- ↑ Gerald Gazdar. " Aplicabilidad de las gramáticas indexadas al lenguaje natural ". En Uwe Reyle y Christian Rohrer, editores, Análisis sintáctico del lenguaje natural y teorías lingüísticas , páginas 69-94. D. Reidel, 1987.
- ↑ Jens Michaelis. « El minimalismo derivacional es ligeramente sensible al contexto ». En Aspectos lógicos de la lingüística computacional, Tercera Conferencia Internacional, LACL 1998, Grenoble, Francia, 14-16 de diciembre de 1998, Artículos seleccionados , volumen 2014 de Lecture Notes in Computer Science , páginas 179-198. Springer, 1998.
- ↑ Pierre Boullier. « Gramáticas de concatenación de rangos ». En Harry C. Bunt, John Carroll y Giorgio Satta (eds.), Nuevos desarrollos en tecnología de análisis sintáctico , volumen 23 de Text, Speech and Language Technology , páginas 269-289. Kluwer Academic Publishers, 2004.
- ↑ Michael J. Fischer. " Gramáticas con producciones tipo macro ". En Noveno Simposio Anual sobre Teoría de la Conmutación y los Autómatas , páginas 131–142, Schenectady, NY, EE. UU., 1968.
- ↑ Günter Hotz y Gisela Pitsch. "Sobre el análisis sintáctico de lenguajes libres de contexto acoplados". Theoretical Computer Science , 161(1–2):205–233, 1996.
- ↑ Owen Rambow y Giorgio Satta. " Una jerarquía bidimensional para sistemas de reescritura paralela ". Informe técnico IRCS-94-02, Universidad de Pensilvania, Filadelfia, EE. UU., 1994.
- Lenguajes formales
