Gramática adjacente à árvore - Tree-adjoining grammar

Gramática de árvore adjacente ( TAG ) é um formalismo gramatical definido por Aravind Joshi . Gramáticas adjacentes à árvore são um tanto semelhantes às gramáticas livres de contexto , mas a unidade elementar de reescrita é a árvore, e não o símbolo. Enquanto as gramáticas livres de contexto têm regras para reescrever símbolos como sequências de outros símbolos, as gramáticas adjacentes a árvores têm regras para reescrever os nós das árvores como outras árvores (ver árvore (teoria dos grafos) e árvore (estrutura de dados) ).

História

TAG originou-se nas investigações de Joshi e seus alunos sobre a família das gramáticas adjuntas (AG), a "gramática das cordas" de Zellig Harris . Os AGs lidam com propriedades exocêntricas da linguagem de uma forma natural e eficaz, mas não têm uma boa caracterização das construções endocêntricas ; o inverso é verdadeiro para gramáticas de reescrita ou gramática de estrutura de frase (PSG). Em 1969, Joshi introduziu uma família de gramáticas que explora essa complementaridade ao misturar os dois tipos de regras. Algumas regras de reescrita muito simples são suficientes para gerar o vocabulário de strings para regras de adjunção. Esta família é distinta da hierarquia de Chomsky-Schützenberger, mas a cruza de maneiras interessantes e linguisticamente relevantes. As cadeias centrais e cadeias adjuntas também podem ser geradas por uma gramática de dependência , evitando as limitações de sistemas de reescrita inteiramente.

Descrição

As regras em um TAG são árvores com um nó folha especial conhecido como nó de pé , que está ancorado em uma palavra. Existem dois tipos de árvores básicas no TAG: árvores iniciais (frequentemente representadas como ' ') e árvores auxiliares (' '). As árvores iniciais representam relações de valência básicas, enquanto as árvores auxiliares permitem a recursão. As árvores auxiliares têm o nó raiz (topo) e o nó dos pés marcados com o mesmo símbolo. Uma derivação começa com uma árvore inicial, combinando por meio de substituição ou adjunção . A substituição substitui um nó de fronteira por outra árvore cujo nó superior tem o mesmo rótulo. O rótulo raiz / pé da árvore auxiliar deve corresponder ao rótulo do nó ao qual está adjacente. A junção pode, portanto, ter o efeito de inserir uma árvore auxiliar no centro de outra árvore.

Outras variantes do TAG permitem árvores com vários componentes , árvores com vários nós de base e outras extensões.

Complexidade e aplicação

Gramáticas-adjacente da árvore são mais poderosos (em termos de capacidade geradora fraco ) do que gramáticas livres de contexto , mas menos potente do que os sistemas lineares livres de contexto de reescrita , indexados ou sensíveis ao contexto gramáticas.

Um TAG pode descrever a linguagem dos quadrados (na qual alguma string arbitrária é repetida) e a linguagem . Este tipo de processamento pode ser representado por um autômato pushdown embutido . Idiomas com cubos (ou seja, strings triplicadas) ou com mais de quatro strings de caracteres distintos de igual comprimento não podem ser gerados por gramáticas adjacentes a árvores.

Por essas razões, as gramáticas adjacentes às árvores são frequentemente descritas como moderadamente sensíveis ao contexto . Essas classes de gramática são conjecturadas como poderosas o suficiente para modelar linguagens naturais, enquanto permanecem analisáveis ​​com eficiência no caso geral.

Equivalências

Vijay-Shanker e Weir (1994) demonstram que gramáticas indexadas lineares , gramática categorial combinatória , gramáticas adjacentes a árvores e gramáticas principais são formalismos fracamente equivalentes , pois todas definem as mesmas linguagens de string.

Lexicalizado

Gramáticas lexicalizadas de árvores adjacentes (LTAG) são uma variante do TAG em que cada árvore elementar (inicial ou auxiliar) está associada a um item lexical. Uma gramática lexicalizada para o inglês foi desenvolvida pelo Grupo de Pesquisa XTAG do Instituto de Pesquisa em Ciência Cognitiva da Universidade da Pensilvânia.

Notas

Referências

links externos