Gramática árvore-adjacente

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa


Ambox grammar.svg
Esta página ou secção precisa de correção ortográfico-gramatical.
Pode conter incorreções textuais, podendo ainda necessitar de melhoria em termos de vocabulário ou coesão, para atingir um nível de qualidade superior conforme o livro de estilo da Wikipédia. Se tem conhecimentos linguísticos, sinta-se à vontade para ajudar.

Gramática árvore-adjacente (TAG) é uma gramática formal definida por Aravind Joshi. Gramáticas árvre-adjacentes são similares às gramáticas chamadas gramáticas livre 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 seqüências de outros símbolos, gramáticas árvore-adjacentes têm regras para reescrever os nós de árvores como outras árvores (veja teoria dos grafos e árvore (estrutura de dados)).

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 lidar com propriedades endocêntricas da linguagem de uma forma natural e eficaz, mas não tem 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. Alguns reescrita muito simples governa suficiente para gerar o vocabulário de cordas para as regras de adjunção. Esta família é diferente da hierarquia de Chomsky, mas cruza-lo de maneiras interessantes e linguisticamente relevante. 2

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

As regras em uma TAG são árvores com um nó folha especial conhecido como o nó-pé, que está ancorada 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.3 Árvores auxiliares têm a (parte superior) e do nó de raiz pé marcado 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. 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 permitir á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ível ao contexto, o que significa que eles possuem certas propriedades que as tornam mais poderoso (em termos de fraca capacidade geradora) do que livre de contexto gramáticas, mas menos potentes do que indexados ou sensível ao contexto. Ligeiramente gramáticas sensíveis ao contexto são conjecturou para ser poderoso o suficiente para modelo linguagem natural, permanecendo de forma eficiente, no caso geral.5

Uma TAG pode descrever a linguagem de quadrados (em que alguns seqüência arbitrária é repetida) e na língua \{a^n b^n c^n d^n | 1 \le n \}. Este tipo de tratamento pode ser representado por um Autômato com pilha embutido.

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ível ao contexto do idioma.

Equivalências[editar | editar código-fonte]

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

Referências

  1. Joshi, Aravind; S. R. Kosaraju, H. Yamada. "String Adjunct Grammars". Proceedings Tenth Annual Symposium on Automata Theory, Waterloo, Canada.
  2. Joshi, Aravind. "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. Speech and Language Processing. Upper Saddle River, NJ: Prentice Hall, 2000. 354 p.
  4. Joshi, Aravind; Owen Rambow (2003). "A Formalism for Dependency Grammar Based on Tree Adjoining Grammar". Proceedings of the Conference on Meaning-Text Theory. 
  5. Joshi, Aravind. In: D. Dowty, L. Karttunen, and A. Zwicky, (eds.). Natural Language Processing: Theoretical, Computational, and Psychological Perspectives. New York, NY: Cambridge University Press, 1985. 206–250 p.
  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.

Links Externos[editar | editar código-fonte]

Predefinição:Formal languages and grammars