En 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 .
Cada formalismo gramatical levemente sensible al contexto define una clase de gramáticas levemente sensibles al contexto (las gramáticas que se pueden especificar en el formalismo) y, por lo tanto, también una clase de lenguajes levemente sensibles al contexto (los lenguajes formales generados por las gramáticas).
En 1985, varios investigadores en lingüística descriptiva y matemática habían proporcionado evidencia 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 señalar el poder formal exacto requerido para la descripción adecuada de la sintaxis del lenguaje natural, Aravind Joshi caracterizó "gramáticas (y lenguajes asociados ) que son sólo un poco más poderosas que las gramáticas libres de contexto (lenguajes libres de contexto)". [3] Llamó a estas gramáticas gramáticas levemente sensibles al contexto y a los lenguajes asociados lenguajes levemente sensibles al contexto .
La caracterización de Joshi de gramáticas levemente sensibles al contexto estaba sesgada hacia su trabajo sobre gramática contigua a árboles (TAG). Sin embargo, junto con sus alumnos Vijay Shanker y David Weir, Joshi pronto descubrió que los TAG son equivalentes, en términos de los lenguajes de cadenas generados, a la gramática principal (HG) introducida de forma independiente. [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 mostraron que la noción de sensibilidad leve al contexto es muy general y no ligado a un formalismo específico.
Los formalismos equivalentes a TAG se generalizaron mediante la introducción de 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 [ se necesita aclaración ] de la jerarquía. Independientemente y casi simultáneamente con LCFRS, Hiroyuki Seki et al. propuso el formalismo esencialmente idéntico de la gramática libre de contexto múltiple (MCFG). [9] LCFRS/MCFG a veces se considera el formalismo más general para especificar gramáticas ligeramente sensibles al contexto. Sin embargo, varios autores han observado que algunas de las propiedades características de los formalismos equivalentes a TAG no se conservan mediante LCFRS/MCFG, [10] y que hay lenguajes que tienen las propiedades características de una leve sensibilidad al contexto 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 lineales libres de contexto bien anidados /gramáticas múltiples libres de contexto, [10] [12] que definen una clase de gramáticas que incluye adecuadamente los formalismos equivalentes a TAG pero que es apropiadamente incluidos en la jerarquía LCFRS/MCFG sin restricciones.
A pesar de una cantidad considerable de trabajo sobre el tema, no existe una definición formal generalmente aceptada de sensibilidad leve al contexto.
Según la caracterización original de Joshi, [3] una clase de gramáticas ligeramente sensibles al contexto debería tener las siguientes propiedades:
Además de esto, se entiende que cada clase de gramáticas ligeramente sensibles al contexto debería poder generar todos los lenguajes libres de contexto.
La caracterización de Joshi no es una definición formal. Él señala: [3]
Esta es sólo una caracterización aproximada porque 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 lo que lo he hecho hasta ahora.
Otros autores han propuesto caracterizaciones alternativas de sensibilidad leve al contexto, algunas de las cuales toman la forma de definiciones formales. Por ejemplo, Laura Kallmeyer [13] adopta la perspectiva de que una leve sensibilidad al contexto debería definirse como una propiedad de clases de lenguas en lugar de, como en la caracterización de Joshi, clases de gramáticas. Esta definición basada en el lenguaje conduce a una noción del concepto diferente a la de Joshi.
El término dependencias entre series se refiere a ciertos patrones característicos de ordenación de palabras, en particular a los patrones verbo-argumento observados en cláusulas subordinadas en holandés [1] y alemán suizo. [2] Estos son los mismos patrones que pueden usarse para argumentar en contra de la libertad de contexto del lenguaje natural; por lo tanto, requerir gramáticas levemente sensibles al contexto para modelar dependencias entre series significa que estas gramáticas deben ser más poderosas que las gramáticas libres de contexto.
Kallmeyer [13] identifica la capacidad de modelar dependencias entre series 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 están libres de contexto, lo que se puede demostrar usando el lema de bombeo .
Un lenguaje formal tiene un crecimiento constante si cada cadena del idioma es más larga que las siguientes cadenas más cortas en como máximo una constante (específica del idioma). A menudo se considera que los lenguajes que violan esta propiedad están más allá de la capacidad humana, aunque algunos autores han argumentado que ciertos fenómenos en el lenguaje natural muestran un crecimiento que no puede limitarse a una constante. [14]
La mayoría de los formalismos gramaticales levemente sensibles al contexto (en particular, LCFRS/MCFG) en realidad satisfacen una propiedad más fuerte que el crecimiento constante llamada semilinealidad . [7] Un lenguaje es semilineal si su imagen bajo el mapeo Parikh (el mapeo que "olvida" la posición relativa de los símbolos en una cadena, tratándolo efectivamente como una bolsa de palabras) es un lenguaje regular . Todos los lenguajes semilineales son de crecimiento constante, pero no todos los lenguajes con crecimiento constante son semilineales. [11]
Se dice que un formalismo gramatical tiene análisis polinomial si su problema de membresía 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 generado 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 el punto de vista de la leve sensibilidad al contexto como una propiedad de las clases de idiomas, el análisis polinomial se refiere al problema de pertenencia al idioma. Este es el problema de decidir, para un lenguaje fijo L , si una cadena determinada w pertenece a L. La complejidad temporal de este problema se mide en términos de la longitud de w ; ignora la pregunta de cómo se especifica L.
Tenga en cuenta que ambas interpretaciones del análisis polinomial son idealizaciones en el sentido de que para aplicaciones prácticas uno está interesado no sólo en la pregunta de sí o no sobre si una oración es gramatical, sino también en la estructura sintáctica que la gramática asigna a la oración.
A lo largo de los años, se han introducido una gran cantidad de formalismos gramaticales que satisfacen algunas o todas las propiedades características propuestas por Joshi. Varios de ellos tienen caracterizaciones alternativas basadas en autómatas que no se analizan en este artículo; por ejemplo, los lenguajes generados por gramática contigua a árboles se pueden caracterizar por autómatas pushdown incorporados .
Los sistemas de reescritura lineales libres de contexto/gramáticas múltiples libres de contexto forman una jerarquía bidimensional de poder generativo con respecto a dos parámetros gramaticales específicos llamados fan-out y ranking . [22] Más precisamente, los lenguajes generados por LCFRS/MCFG con distribución en abanico f ≥ 1 y rango r ≥ 3 se incluyen adecuadamente en la clase de lenguajes generados por LCFRS/MCFG con rango r + 1 y distribución en abanico f , como así como la clase de lenguajes generados por LCFRS/MCFG con rango r y despliegue f + 1 . En presencia de un buen anidamiento, esta jerarquía colapsa a una jerarquía unidimensional con respecto al despliegue; esto se debe a que cada LCFRS/MCFG bien anidado se puede transformar en un LCFRS/MCFG bien anidado equivalente con el mismo despliegue y rango 2. [10] [12] Dentro de la jerarquía LCFRS/MCFG, los lenguajes libres de contexto se puede caracterizar por las gramáticas con despliegue 1; Para este despliegue no hay diferencia entre gramáticas generales y gramáticas bien anidadas. Los formalismos equivalentes a TAG se pueden caracterizar como LCFRS/MCFG bien anidados de distribución 2.
