La gramática de árboles adyacentes ( TAG ) es un formalismo gramatical definido por Aravind Joshi . Las gramáticas de árboles adyacentes son algo similares a las gramáticas libres de contexto , pero la unidad elemental de reescritura es el árbol en lugar del símbolo. Mientras que las gramáticas libres de contexto tienen reglas para reescribir símbolos como cadenas de otros símbolos, las gramáticas de árboles adyacentes tienen reglas para reescribir los nodos de los árboles como otros árboles (ver árbol (teoría de grafos) y árbol (estructura de datos) ).
TAG se originó en investigaciones de Joshi y sus estudiantes sobre la familia de gramáticas de adjunción (AG), [1] la "gramática de cadenas" de Zellig Harris . [2] Las AG manejan propiedades exocéntricas del lenguaje de una manera natural y efectiva, pero no tienen una buena caracterización de las construcciones endocéntricas ; lo inverso es cierto para las gramáticas de reescritura o gramática de estructura de frase (PSG). En 1969, Joshi introdujo una familia de gramáticas que explota esta complementariedad mezclando los dos tipos de reglas. Unas pocas reglas de reescritura muy simples son suficientes para generar el vocabulario de cadenas para las reglas de adjunción. Esta familia es distinta de la jerarquía de Chomsky-Schützenberger pero la cruza de maneras interesantes y lingüísticamente relevantes. [3] Las cadenas centrales y las cadenas adjuntas también pueden generarse mediante una gramática de dependencia , evitando por completo las limitaciones de los sistemas de reescritura. [4] [5]
Las reglas en un TAG son árboles con un nodo de hoja especial conocido como nodo de pie , que está anclado a una palabra. Hay dos tipos de árboles básicos en TAG: árboles iniciales (a menudo representados como ' ') y árboles auxiliares (' '). Los árboles iniciales representan relaciones de valencia básicas, mientras que los árboles auxiliares permiten la recursión. [6] Los árboles auxiliares tienen el nodo raíz (superior) y el nodo de pie etiquetados con el mismo símbolo. Una derivación comienza con un árbol inicial, que se combina mediante sustitución o adjunción . La sustitución reemplaza un nodo de frontera con otro árbol cuyo nodo superior tiene la misma etiqueta. La etiqueta raíz/pie del árbol auxiliar debe coincidir con la etiqueta del nodo al que se une. La adjunción puede tener el efecto de insertar un árbol auxiliar en el centro de otro árbol. [4]
Otras variantes de TAG permiten árboles multicomponentes, árboles con múltiples nodos de pie y otras extensiones.
Las gramáticas contiguas a árboles son más poderosas (en términos de capacidad generativa débil ) que las gramáticas libres de contexto , pero menos poderosas que los sistemas de reescritura lineales libres de contexto , [7] indexados [nota 1] o las gramáticas sensibles al contexto .
Una etiqueta puede describir el lenguaje de cuadrados (en el que se repite una cadena arbitraria) y el lenguaje . Este tipo de procesamiento se puede representar mediante un autómata de inserción incorporado . Los lenguajes con cubos (es decir, cadenas triplicadas) o con más de cuatro cadenas de caracteres distintas de igual longitud no se pueden generar mediante gramáticas de árboles adyacentes.
Por estas razones, las gramáticas que se unen a árboles suelen describirse como ligeramente sensibles al contexto . Se supone que estas clases de gramática son lo suficientemente potentes como para modelar lenguajes naturales y, al mismo tiempo, seguir siendo eficientemente analizables en el caso general. [8]
Vijay-Shanker y Weir (1994) [9] demuestran que las gramáticas indexadas lineales , la gramática categorial combinatoria , las gramáticas contiguas a árboles y las gramáticas principales son formalismos débilmente equivalentes , ya que todas definen los mismos lenguajes de cadenas.
Las gramáticas lexicalizadas de árboles adyacentes (LTAG) son una variante de TAG en la que cada árbol elemental (inicial o auxiliar) está asociado a un elemento léxico. El grupo de investigación XTAG del Instituto de Investigación en Ciencias Cognitivas de la Universidad de Pensilvania ha desarrollado una gramática lexicalizada para el inglés. [5]
