Gramática adyacente al árbol
La gramática adyacente al árbol ( TAG ) es un formalismo gramatical definido por Aravind Joshi . Las gramáticas adyacentes a árboles 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 adyacentes a árboles tienen reglas para reescribir los nodos de árboles como otros árboles (ver árbol (teoría de grafos) y árbol (estructura de datos) ).
TAG se originó en las investigaciones de Joshi y sus estudiantes sobre la familia de gramáticas adjuntas (AG), [1] la "gramática de cuerdas" de Zellig Harris . [2] Los AG manejan las propiedades exocéntricas del lenguaje de una manera natural y efectiva, pero no tienen una buena caracterización de las construcciones endocéntricas ; lo contrario ocurre con las gramáticas de reescritura o la gramática de estructura de frases (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 reglas adjuntas. Esta familia es distinta de laLa jerarquía de Chomsky-Schützenberger, pero la cruza de formas interesantes y lingüísticamente relevantes. [3] Las cadenas centrales y las cadenas adjuntas también se pueden generar 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 recursividad. [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 de raíz / pie del árbol auxiliar debe coincidir con la etiqueta del nodo al que se une. Por tanto, 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 de varios componentes , árboles con múltiples nodos de pie y otras extensiones.
Las gramáticas adyacentes 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 lineal libres de contexto , [7] indexadas [nota 1] o gramáticas sensibles al contexto.
Un TAG puede describir el idioma de los cuadrados (en el que se repite alguna cadena arbitraria) y el idioma . Este tipo de procesamiento se puede representar mediante un autómata pushdown integrado . 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 adyacentes a árboles.
