Gramática contigua al árbol
La gramática contigua al árbol ( TAG ) es un formalismo gramatical definido por Aravind Joshi . Las gramáticas contiguas 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 contiguas 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 manera natural y efectiva, pero no tienen una buena caracterización de las construcciones endocéntricas ; lo contrario 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 lajerarquí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 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. 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 múltiples componentes , á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 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 incrustado . Los lenguajes con cubos (es decir, cadenas triplicadas) o con más de cuatro cadenas de caracteres distintas de igual longitud no pueden generarse mediante gramáticas de árboles contiguos.
