Formalismo gramatical moderadamente sensível ao contexto - Mildly context-sensitive grammar formalism

Em linguística computacional , o termo formalismos gramaticais moderadamente sensíveis ao contexto refere-se a vários formalismos gramaticais que foram desenvolvidos em um esforço para fornecer descrições adequadas da estrutura sintática da linguagem natural .

Todo formalismo gramatical moderadamente sensível ao contexto define uma classe de gramáticas moderadamente sensíveis ao contexto (as gramáticas que podem ser especificadas no formalismo) e, portanto, também uma classe de linguagens moderadamente sensíveis ao contexto (as linguagens formais geradas pelas gramáticas).

Fundo

Em 1985, vários pesquisadores em linguística descritiva e matemática forneceram evidências contra a hipótese de que a estrutura sintática da linguagem natural pode ser adequadamente descrita por gramáticas livres de contexto . Ao mesmo tempo, o passo para o próximo nível da hierarquia de Chomsky , para as gramáticas sensíveis ao contexto , parecia desnecessário e indesejável. Em uma tentativa de apontar o poder formal exato necessário para a descrição adequada da sintaxe da linguagem natural, Aravind Joshi caracterizou "gramáticas (e linguagens associadas ) que são apenas ligeiramente mais poderosas do que gramáticas livres de contexto (linguagens livres de contexto)". Ele chamou essas gramáticas de gramáticas sensíveis ao contexto e as línguas associadas de linguagens sensíveis ao contexto .

A caracterização de Joshi de gramáticas moderadamente sensíveis ao contexto foi tendenciosa para seu trabalho na gramática adjacente à árvore (TAG). No entanto, junto com seus alunos Vijay Shanker e David Weir, Joshi logo descobriu que os TAGs são equivalentes, em termos de linguagens de string geradas, à gramática principal (HG) introduzida independentemente . Isso foi seguido por dois resultados de equivalência semelhantes, para gramática indexada linear (LIG) e gramática categorial combinatória (CCG), que mostraram que a noção de sensibilidade ao contexto leve é ​​muito geral e não está ligada a um formalismo específico.

Os formalismos equivalentes a TAG foram generalizados pela introdução de sistemas lineares de reescrita livre de contexto (LCFRS). Essas gramáticas definem uma hierarquia infinita de linguagens de string entre as linguagens livres de contexto e as sensíveis ao contexto, com as linguagens geradas pelos formalismos TAG equivalentes na extremidade inferior da hierarquia. Independentemente e quase simultaneamente do LCFRS, Hiroyuki Seki et al. propôs o formalismo essencialmente idêntico de gramática livre de contexto múltipla (MCFG). LCFRS / MCFG é às vezes considerado o formalismo mais geral para especificar gramáticas moderadamente sensíveis ao contexto. No entanto, vários autores notaram que algumas das propriedades características dos formalismos TAG equivalentes não são preservadas por LCFRS / MCFG, e que existem linguagens que têm as propriedades características de sensibilidade ao contexto moderada, mas não são geradas por LCFRS / MCFG.

Nos últimos anos, tem visto um interesse crescente na classe restrita de sistemas de reescrita sem contexto linear bem aninhados / gramáticas livres de contexto múltiplas, que definem uma classe de gramáticas que inclui adequadamente os formalismos TAG equivalentes, mas está devidamente incluída no LCFRS / irrestrito Hierarquia MCFG.

Caracterização

Apesar de uma quantidade considerável de trabalho sobre o assunto, não existe uma definição formal geralmente aceita de sensibilidade ao contexto leve.

De acordo com a caracterização original de Joshi, uma classe de gramáticas moderadamente sensíveis ao contexto deve ter as seguintes propriedades:

  1. dependências cross-serial limitadas
  2. crescimento constante
  3. análise polinomial

Além disso, entende-se que cada classe de gramáticas moderadamente sensíveis ao contexto deve ser capaz de gerar todas as linguagens livres de contexto.

A caracterização de Joshi não é uma definição formal. Ele observa:

Esta é apenas uma caracterização aproximada porque as condições 1 e 3 dependem das gramáticas, enquanto a condição 2 depende dos idiomas; além disso, a condição 1 precisa ser especificada com muito mais precisão do que fiz até agora.

Outros autores propuseram caracterizações alternativas de leve sensibilidade ao contexto, algumas das quais assumem a forma de definições formais. Por exemplo, Laura Kallmeyer assume a perspectiva de que a sensibilidade ao contexto moderada deve ser definida como uma propriedade de classes de línguas em vez de, como na caracterização de Joshi, classes de gramáticas. Essa definição baseada na linguagem leva a uma noção do conceito diferente da de Joshi.

Dependências de série cruzada

O termo dependências seriais cruzadas refere-se a certos padrões característicos de ordenação de palavras, em particular aos padrões verbo-argumento observados em orações subordinadas em holandês e alemão suíço. Esses são os próprios padrões que podem ser usados ​​para argumentar contra a liberdade de contexto da linguagem natural; portanto, exigir gramáticas moderadamente sensíveis ao contexto para modelar dependências entre séries significa que essas gramáticas devem ser mais poderosas do que gramáticas livres de contexto.

Kallmeyer identifica a capacidade de modelar dependências de série cruzada com a capacidade de gerar a linguagem de cópia

e suas generalizações para duas ou mais cópias de  w , até algum limite. Essas linguagens não são livres de contexto, o que pode ser mostrado usando o lema do bombeamento .

Crescimento constante

Uma linguagem formal é de crescimento constante se cada string na linguagem for maior do que as próximas strings mais curtas em no máximo uma constante (específica da linguagem). As línguas que violam essa propriedade são freqüentemente consideradas além da capacidade humana, embora alguns autores argumentem que certos fenômenos na linguagem natural mostram um crescimento que não pode ser limitado por uma constante.

A maioria dos formalismos gramaticais moderadamente sensíveis ao contexto (em particular, LCFRS / MCFG) na verdade satisfazem uma propriedade mais forte do que o crescimento constante chamado semilinearidade . Uma linguagem é semilinear se sua imagem sob o mapeamento Parikh (o mapeamento que "esquece" a posição relativa dos símbolos em uma string, tratando-a efetivamente como um saco de palavras) é uma linguagem regular . Todas as línguas semilineares são de crescimento constante, mas nem todas as línguas com crescimento constante são semilineares.

Análise polinomial

Diz-se que um formalismo gramatical possui análise sintática polinomial se seu problema de pertinência puder ser resolvido em tempo polinomial determinístico . Este é o problema de decidir, dada uma gramática G escrita no formalismo e uma string  w , se w é gerado pelo  G - isto é, se w é "gramatical" de acordo com  G . A complexidade de tempo desse problema é medida em termos do tamanho combinado de  G e  w .

Sob a visão da sensibilidade ao contexto moderada como uma propriedade de classes de linguagens, a análise polinomial se refere ao problema de associação de linguagem. Este é o problema de decidir, para uma linguagem fixa  L , se uma determinada string  w pertence a  L . A complexidade de tempo desse problema é medida em termos do comprimento de  w ; ele ignora a questão de como L é especificado.

Observe que ambos os entendimentos de análise polinomial são idealizações no sentido de que, para aplicações práticas, estamos interessados ​​não apenas na questão sim / não se uma frase é gramatical, mas também na estrutura sintática que a gramática atribui à frase.

Formalismos

Com o passar dos anos, foi introduzido um grande número de formalismos gramaticais que satisfazem algumas ou todas as propriedades características apresentadas por Joshi. Vários deles têm caracterizações alternativas baseadas em autômatos que não são discutidas neste artigo; por exemplo, as linguagens geradas pela gramática adjacente à árvore podem ser caracterizadas por autômatos pushdown integrados .

Formalismos equivalentes a TAG

Formalismos equivalentes a LCFRS / MCFG geral

Formalismos equivalentes a LCFRS / MCFG bem aninhados

  • Gramáticas macro não duplicadas
  • Gramáticas livres de contexto acopladas (CCFG)
  • Sistemas de reescrita sem contexto linear bem aninhados
  • Gramáticas livres de contexto bem aninhadas

Relações entre os formalismos

Sistemas de reescrita sem contexto linear / gramáticas sem contexto múltiplas formam uma hierarquia bidimensional de poder generativo com respeito a dois parâmetros específicos da gramática chamados fan-out e classificação . Mais precisamente, as linguagens geradas por LCFRS / MCFG com fan-out  f  ≥ 1 e rank  r  ≥ 3 estão devidamente incluídas na classe de linguagens geradas por LCFRS / MCFG com rank  r  + 1 e fan-out  f , bem como o classe de linguagens geradas por LCFRS / MCFG com rank  r e fan-out  f  + 1 . Na presença de um aninhamento adequado, essa hierarquia se reduz a uma hierarquia unidimensional em relação ao espalhamento; isso ocorre porque cada LCFRS / MCFG bem aninhado pode ser transformado em um LCFRS / MCFG bem aninhado equivalente com o mesmo fan-out e classificação 2. Dentro da hierarquia LCFRS / MCFG, as linguagens livres de contexto podem ser caracterizadas pelas gramáticas com fan-out 1; para este fan-out, não há diferença entre gramáticas gerais e bem-aninhadas. Os formalismos equivalentes a TAG podem ser caracterizados como LCFRS / MCFG bem aninhado de fan-out 2.

Veja também

Referências

  1. ^ a b Riny Huybregts. "The Weak Inadequacy of Context-Free Phrase Structure Grammars". Em Ger de Haan, Mieke Trommelen e Wim Zonneveld, editores, Van periferie naar kern , páginas 81-99. Foris, Dordrecht, Holanda, 1984.
  2. ^ a b Stuart M. Shieber. " Evidence Against the Context-Freeness of Natural Language ". Linguistics and Philosophy , 8 (3): 333-343, 1985.
  3. ^ a b c d Aravind K. Joshi. " Tree Adjoining Grammars: Quanta sensibilidade ao contexto é necessária para fornecer descrições estruturais razoáveis? ". Em David R. Dowty, Lauri Karttunen e Arnold M. Zwicky, editores, Natural Language Parsing , páginas 206-250. Cambridge University Press, 1985.
  4. ^ David J. Weir, K. Vijay-Shanker e Aravind K. Joshi. " A relação entre gramáticas adjacentes de árvore e gramáticas principais ". Em Proceedings of the 24th Annual Meeting of the Association for Computational Linguistics (ACL) , páginas 67-74, New York, USA, 1986.
  5. ^ K. Vijay-Shanker. " A Study of Tree Adjoining Grammars ". Ph.D. tese, Universidade da Pensilvânia, Filadélfia, EUA, 1987.
  6. ^ a b David J. Weir e Aravind K. Joshi. " Gramáticas Categóricas Combinatórias: Poder Gerativo e Relação com Sistemas de Reescrita Lineares Livres de Contexto ". Em Proceedings of the 26th Annual Meeting of the Association for Computational Linguistics (ACL) , páginas 278-285, Buffalo, EUA, 1988.
  7. ^ a b c d K. Vijay-Shanker, David J. Weir, e Aravind K. Joshi. " Caracterizando descrições estruturais produzidas por vários formalismos gramaticais ". Em Proceedings of the 25th Annual Meeting ofthe Association for Computational Linguistics (ACL) , páginas 104-111, Stanford, CA, EUA, 1987.
  8. ^ a b David J. Weir. " Caracterizando formalismos gramaticais sensíveis ao contexto moderado ". Ph.D. tese, Universidade da Pensilvânia, Filadélfia, EUA, 1988.
  9. ^ a b Hiroyuki Seki, Takashi Matsumura, Mamoru Fujii e Tadao Kasami. " On Multiple Context-Free Grammars ". Theoretical Computer Science , 88 (2): 191–229, 1991.
  10. ^ a b c d Makoto Kanazawa. " O lema do bombeamento para várias linguagens livres de contexto bem aninhadas ". Em Desenvolvimentos na Teoria da Linguagem. 13ª Conferência Internacional, DLT 2009, Stuttgart, Alemanha, 30 de junho a 3 de julho de 2009. Proceedings , volume 5583 de Lecture Notes in Computer Science , páginas 312-325, 2009.
  11. ^ a b Laura Kallmeyer. " Sobre reescrita não linear sensível ao contexto moderada ". Research on Language and Computation , 8 (4): 341–363, 2010.
  12. ^ a b c Carlos Gómez-Rodríguez, Marco Kuhlmann e Giorgio Satta. " Análise eficiente de sistemas de reescrita lineares bem aninhados e livres de contexto ". Em Proceedings of Human Language Technologies: The 2010 Annual Conference of North American Chapter da Association for Computational Linguistics (NAACL) , páginas 276-284, Los Angeles, EUA, 2010.
  13. ^ a b Laura Kallmeyer. Análise além das gramáticas livres de contexto . Springer, 2010.
  14. ^ Jens Michaelis e Marcus Kracht. " Semilinearidade como uma invariante sintática ". Em Aspectos Lógicos da Lingüística Computacional. First International Conference, LACL 1996, Nancy, France, 23-25 ​​de setembro de 1996. Selected Papers , volume 1328 de Lecture Notes in Computer Science , páginas 329-345. Springer, 1997.
  15. ^ Carl J. Pollard . "Gramáticas de estrutura de frase generalizadas, gramáticas principais e linguagem natural". Ph.D. tese, Stanford University, 1984.
  16. ^ Kelly Roach. " Formal Properties of Head Grammars ". Em Alexis Manaster-Ramer, editor, Mathematics of Language , páginas 293–347. John Benjamins, 1987.
  17. ^ Gerald Gazdar. " Aplicabilidade de gramáticas indexadas à linguagem natural ". Em Uwe Reyle e Christian Rohrer, editores, Natural Language Parsing and Linguistic Theories , páginas 69-94. D. Reidel, 1987.
  18. ^ Jens Michaelis. " Derivational Minimalism Is Mildly Context-Sensitive ". Em Logical Aspects of Computational Linguistics, Third International Conference, LACL 1998, Grenoble, France, 14-16 de dezembro de 1998, Selected Papers , volume 2014 de Lecture Notes in Computer Science , páginas 179-198. Springer, 1998.
  19. ^ Pierre Boullier. " Gramáticas de concatenação de intervalo ". Em Harry C. Bunt, John Carroll e Giorgio Satta, editores, New Developments in Parsing Technology , volume 23 de Text, Speech and Language Technology , páginas 269-289. Kluwer Academic Publishers, 2004.
  20. ^ Michael J. Fischer. " Gramáticas com produções semelhantes a macro ". In Ninth Annual Symposium on Switching and Automata Theory , páginas 131-142, Schenectady, NY, USA, 1968.
  21. ^ Günter Hotz e Gisela Pitsch. "On Parsing Coupled-Context-Free Languages". Theoretical Computer Science , 161 (1-2): 205-233, 1996.
  22. ^ Owen Rambow e Giorgio Satta. " Uma hierarquia bidimensional para sistemas de reescrita paralela ". Relatório Técnico IRCS-94-02, Universidade da Pensilvânia, Filadélfia, EUA, 1994.