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 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).
En 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 de señalar con precisión el poder formal exacto necesario para la descripción adecuada de la sintaxis del lenguaje natural, Aravind Joshi caracterizó "gramáticas (y lenguajes asociados ) que son sólo 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 de Joshi de las gramáticas ligeramente sensibles al contexto estaba sesgada hacia su trabajo sobre la gramática de árboles adyacentes (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 introducida independientemente (HG). [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 al contexto leve es muy general y no está vinculada 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 [ aclaración necesaria ] de la jerarquía. Independientemente y casi simultáneamente con LCFRS, Hiroyuki Seki et al. propusieron el formalismo esencialmente idéntico de 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 notado que algunas de las propiedades características de los formalismos equivalentes a TAG no se conservan con LCFRS/MCFG, [10] y que hay lenguajes que tienen las propiedades características de una ligera sensibilidad al contexto pero no se generan con LCFRS/MCFG. [11]
En los últimos años ha aumentado el interés en la clase restringida de sistemas de reescritura lineal libre de contexto 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á incluida adecuadamente en la jerarquía LCFRS/MCFG sin restricciones.
A pesar de la considerable cantidad de trabajo sobre el tema, no existe una definición formal generalmente aceptada de sensibilidad contextual 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:
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 la sensibilidad moderada al contexto, algunas de las cuales adoptan la forma de definiciones formales. Por ejemplo, Laura Kallmeyer [13] adopta la perspectiva de que la sensibilidad moderada al contexto debería definirse como una propiedad de las clases de lenguajes en lugar de, como en la caracterización de Joshi, 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.
El término dependencias entre series se refiere a ciertos patrones característicos de ordenamiento de palabras, en particular a los patrones verbo-argumento observados en las cláusulas subordinadas en holandés [1] y alemán suizo [2] . Estos son los mismos patrones que se pueden usar para argumentar en contra de la independencia de contexto del lenguaje natural; por lo tanto, requerir gramáticas ligeramente sensibles al contexto para modelar las 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 son libres de contexto, lo que se puede demostrar utilizando el lema de bombeo .
Un lenguaje formal es de crecimiento constante si cada cadena de caracteres que lo compone es más larga que la cadena siguiente más corta, como máximo en una constante (específica del lenguaje). Los lenguajes que violan esta propiedad suelen considerarse que están más allá de la capacidad humana, aunque algunos autores han argumentado que ciertos fenómenos del lenguaje natural sí muestran un crecimiento que no puede limitarse mediante una constante. [14]
La mayoría de los formalismos gramaticales ligeramente 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 la función Parikh (la función 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 todos los lenguajes con crecimiento constante son semilineales. [11]
Se dice que un formalismo gramatical tiene análisis polinomial si su problema de pertenencia se puede resolver en tiempo polinomial determinista . Este es el problema para 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 sensibilidad moderada al contexto como propiedad de las clases de lenguajes, el análisis sintáctico polinomial se refiere al problema de pertenencia al lenguaje. Este es el problema para decidir, para un lenguaje fijo L , si una cadena dada w pertenece a L . La complejidad temporal de este problema se mide en términos de la longitud de w ; ignora la cuestión de cómo se especifica L .
Obsérvese que ambas concepciones del análisis sintáctico 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áticas de contigüidad de árboles se pueden caracterizar mediante autómatas de inserción incorporados .
Los sistemas de reescritura lineal libre de contexto/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 idiomas generados por LCFRS/MCFG con fan-out f ≥ 1 y rango r ≥ 3 se incluyen adecuadamente en la clase de idiomas generados por LCFRS/MCFG con rango r + 1 y fan-out f , así como en la clase de idiomas generados por LCFRS/MCFG con rango r y fan-out f + 1 . En presencia de una buena anidación, esta jerarquía colapsa a una jerarquía unidimensional con respecto a fan-out; Esto se debe a que cada LCFRS/MCFG bien anidado se puede transformar en un LCFRS/MCFG bien anidado equivalente con el mismo abanico de salida y rango 2. [10] [12] Dentro de la jerarquía LCFRS/MCFG, los lenguajes libres de contexto se pueden caracterizar por las gramáticas con abanico de salida 1; para este abanico de salida no hay diferencia entre gramáticas generales y bien anidadas. Los formalismos equivalentes a TAG se pueden caracterizar como LCFRS/MCFG bien anidados de abanico de salida 2.
