# Gramática árvore-adjacente

Gramática árvore-adjacente (TAG) é uma gramática formal definida por Aravind Joshi. Gramáticas árvore-adjacentes são similares às gramáticas livres de contexto, mas a unidade elementar de reescrita é uma árvore, em vez de um símbolo. Considerando as gramáticas livres de contexto, estas têm regras para os símbolos de reescrita como sequências de outros símbolos, enquanto gramáticas árvore-adjacentes têm regras para reescrever os nós de árvores como outras árvores (veja teoria dos grafos e árvore).

## História

TAG foi originada nas investigações por Joshi e seus alunos enquanto estudavam a família de gramáticas adjacentes (AG), a "gramática de string" de Zellig Harris. AGs lidam com propriedades endocêntricas da linguagem de uma forma natural e eficaz, mas não têm uma boa caracterização das construções excêntricas. O inverso é verdadeiro em gramáticas de reescrita. Em 1969, Joshi introduziu uma família de gramáticas que explora esta complementaridade por mistura dos dois tipos de regras. Algumas reescritas muito simples regem o suficiente para gerar o vocabulário de cordas para as regras de adjunção. Esta família é diferente da hierarquia de Chomsky, mas interliga-se de maneiras interessantes e linguisticamente relevantes.

## Descrição

As regras em uma TAG são árvores com um nó folha especial, conhecido como nó-pé, que está ancorado a uma palavra. Existem dois tipos básicos de árvores em TAG: árvores iniciais (frequentemente representadas por '$\alpha$') e árvores auxiliares ('$\beta$'). Árvores iniciais representam relações básicas de valência, enquanto as árvores auxiliares permitem a recursão. Árvores auxiliares têm a parte superior e o nó de raiz pé marcados com o mesmo símbolo. A derivação começa com uma árvore inicial, combinando via "ou substituição ou adjunção". "Substituição" substitui um nó fronteira com outra árvore cujo nó superior tem o mesmo rótulo; e "Adjunção" insere uma árvore auxiliar no centro de uma outra árvore.
A etiqueta de raiz/pé da árvore auxiliar deve coincidir com o rótulo do nó no qual é adjacente. Outras variantes do TAG permitem árvores multi-componentes, árvores com vários nós de pé e outras extensões.

## Complexidade e aplicação

Gramáticas de árvores adjacentes são frequentemente descritas como "levemente sensíveis ao contexto", o que significa que eles possuem certas propriedades que as tornam mais poderosas (em termos de fraca capacidade geradora) do que livre de contexto gramatical, mas menos potentes do que indexadas ou sensíveis ao contexto. Ligeiramente, gramáticas sensíveis ao contexto são conjecturadas para serem poderosas o suficiente para um modelo de linguagem natural, permanecendo de forma eficiente, no caso geral.
Uma TAG pode descrever a linguagem de quadrados (em que alguma sequência arbitrária é repetida) e na língua $\{a^{n}b^{n}c^{n}d^{n}|1\leq n\}$. Este tipo de tratamento pode ser representado por um autômato com pilha embutida.
Linguagens com cubos (ou seja, cadeias triplicadas) ou com mais de quatro cadeias de caracteres distintos de igual comprimento não podem ser geradas por gramáticas árvore-adjacentes.
Por estas razões, as linguagens geradas por gramáticas árvore-adjacentes são conhecidas como "levemente sensíveis ao contexto do idioma".

### Equivalências

Vijay-Shanker e Weir (1994) demonstram que gramáticas indexadas linearmente, Gramáticas de Categorias Combinatórias, Gramáticas Árvore-adjacentes e Gramáticas de Cabeça são formalismos fracamente equivalentes, que definem as mesmas linguagens.