Gramática árvore-adjacente

Origem: Wikipédia, a enciclopédia livre.

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[editar | editar código-fonte]

TAG foi originada nas investigações por Joshi e seus alunos enquanto estudavam a família de gramáticas adjacentes (AG),[1] 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.[2]

Descrição[editar | editar código-fonte]

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 '') e árvores auxiliares (''). Árvores iniciais representam relações básicas de valência, enquanto as árvores auxiliares permitem a recursão.[3] Á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.[4]

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[editar | editar código-fonte]

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.[5]

Uma TAG pode descrever a linguagem de quadrados (em que alguma sequência arbitrária é repetida) e na língua . 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[editar | editar código-fonte]

Vijay-Shanker e Weir (1994)[6] 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.

Referências

  1. ↑ Joshi, Aravind; S. R. Kosaraju, H. Yamada (1969). «String Adjunct Grammars». Proceedings Tenth Annual Symposium on Automata Theory, Waterloo, Canada 
  2. ↑ Joshi, Aravind (1969). «Properties of Formal Grammars with Mixed Types of Rules and Their Linguistic Relevance». Proceedings Third International Symposium on Computational Linguistics, Stockholm, Sweden 
  3. ↑ Jurafsky, Daniel; James H. Martin (2000). Speech and Language Processing. Upper Saddle River, NJ: Prentice Hall. 354 páginas 
  4. ↑ Joshi, Aravind; Owen Rambow (2003). «A Formalism for Dependency Grammar Based on Tree Adjoining Grammar» (PDF). Proceedings of the Conference on Meaning-Text Theory 
  5. ↑ Joshi, Aravind (1985). «How much context-sensitivity is necessary for characterizing structural descriptions». In: D. Dowty, L. Karttunen, and A. Zwicky, (eds.). Natural Language Processing: Theoretical, Computational, and Psychological Perspectives. New York, NY: Cambridge University Press. pp. 206–250 
  6. ↑ Vijay-Shanker, K. and Weir, David J. 1994. The Equivalence of Four Extensions of Context-Free Grammars. Mathematical Systems Theory 27(6): 511–546.

Ligações externas[editar | editar código-fonte]

  • The XTAG project, que usa uma TAG para processamento de linguagem natural.
  • A tutorial on TAG
  • Another tutorial, com foco na comparação com Lexical Functional Grammar e extração de gramáticas do Treebank.
  • SemConst Documentation Um levantamento rápido sobre a problemática da Sintaxe e Interface Semântica dentro do framework TAG.
  • The TuLiPa project A arquitetura de análise linguística de Tübingen (TuLiPA) é um ambiente de análise sintática (e semântica) multiformal, projetado principalmente para gramáticas adjacentes de árvore de vários componentes com tuplas de árvore.
  • The Metagrammar Toolkit, que fornece várias ferramentas para editar e compilar MetaGrammars em TAGs. Também inclui uma ampla cobertura de Metagramáticas Francesas.
  • LLP2 Um analisador gramatical adjacente à árvore lexicalizada que fornece um ambiente gráfico fácil de usar (página em francês).
Obtida de "https://pt.wikipedia.org/w/index.php?title=Gramática_árvore-adjacente&oldid=64094643"