Wikipédia

Gramática moderadamente sensível ao contexto

Em Linguística Computacional, o termo Formalismos de Gramáticas Moderadamente sensíveis ao contexto — tradução livre de mildly context-sensitive grammar formalisms — se refere a várias gramáticas formais desenvolvidas numa tentativa de proporcionar uma descrição linguística da estrutura sintática da linguagem natural.

Todos os formalismos de gramática moderadamente sensível ao contexto definem uma classe de Gramáticas Moderadamente sensíveis ao contexto (As gramáticas que podem ser descritas de modo formal), e além disso uma classe de Linguagens Moderadamente sensíveis ao contexto (A linguagem Formal gerada pelas gramáticas).

História editar

Em 1985, vários pesquisadores de linguística matemática e linguística descritiva forneceram evidencia contra a hipótese de que estrutura sintática da linguagem natural poderia ser adequadamente descrita por gramáticas livre de contexto.[1][2] Ao mesmo tempo, o passo para o próximo nível da Hierarquia de Chomsky, para gramáticas sensíveis ao contexto, parecia desnecessário e indesejado.

Em uma tentativa de descobrir o exato poder formal necessário para a descrição adequada da sintaxe da linguagem natural, Aravind Joshi definiu ‘gramáticas (e associou linguagens) que são levemente mais poderosas que gramáticas/linguagens livre de contexto’.[3] Ele chamou essas de gramáticas e respectivas linguagens de moderadamente sensíveis ao contexto.

A descrição, feita por Joshi, de gramáticas moderadamente sensíveis ao contexto foi voltada para seus trabalho em Gramática Árvore-adjacente (TAG, do termo inglês Tree-Adjoining Grammar). Contudo, junto com seus estudantes Vijay Shanker e David Weir, Joshi descobriu que TAGs eram equivalentes, em termos das linguagens de cadeias geradas, a Gramática de cabeça(HG, do inglês Head Grammar),introduzida independentemente.[4] Seguido por 2 resultados equivalentes, para Gramática indexada (LIG, do inglês linear indexed grammar) [5] e gramática categorial combinatória (CGC, do inglês combinatory categorial grammar), [6] que mostrou que a noção de moderadamente sensível ao contexto é muito geral e não atada a um formalismo específico.

As descrições formais de gramáticas equivalentes às de Gramáticas de Árvore Adjacente foram generalizadas pela introdução de gramática livre do contexto generalizada (LCFRS, de linear context-free rewriting system).[7][8]

Essas gramáticas definem um hierarquia infinita de linguagens entre as livres de contexto e das sensíveis ao contexto, com as linguagens geradas pelo modelo formal de gramáticas de árvore-adjacente no nível mais baixo da hierarquia. Independente e quase simultaneamente à gramática livre do contexto generalizada, Hiroyuki Seki et al. propôs a descrição formal praticamente idêntica de gramática, a chamada livre de contexto múltipla (MCFG, do inglês multiple context-free grammar).[9]

LCFRS/MCFG é algumas vezes considerado como o modelo formal mais geral para definição de gramaticas moderadamente sensível ao contexto. Contudo, vários autores notaram que algumas das propriedades características de descrições formais equivalentes de gramáticas de árevore-adjacente não são preservadas pelo LCFRS/MCFG, [10] e que há linguagens que tem propriedades características de serem moderadadamente sensiveis ao contexto mas não são geradas por LCFRS/MCFG.[11]

Nos últimos anos, tem crescido o interesse na classe restrita de gramáticas LCFRS/MCFG bem aninhadas (tradução livre de well-nested),[10][12] que define uma classe de gramáticas que inclui devidamente a descrição formal de gramáticas de árvore-adjacente e também inclui na irrestrita hierarquia de LCFRS/MCFG.

Definição editar

Apesar de uma quantidade considerável de trabalhos sobre o tema, não há definição formal aceita por todos de sensibilidade ao contexto moderada.

De acordo com a caracterização original de Joshi, [3] uma classe de gramáticas moderadamente sensivél ao contexto deve ter as seguintes propriedades:

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

Além disso, sabe-se que toda classe de gramáticas moderadamente sensível ao contexto deve conseguir gerar todas as linguagens livres de contexto.

A definição de Joshi não é formal. Citação do mesmo, em tradução livre:[3]

Outros autores tem proposto definições alternativas da sensibilidade ao contexto moderada, alguns têm definições formais. Por exemplo, Laura Kallmeyer[13] tem a perspectiva de que sensibilidade ao contexto moderada deve ser mais definida como uma propriedade de uma classe de linguagens do que como uma classes de gramáticas, como Joshi sugere. Uma definição de baseada na linguagem aponta para uma noção diferente do conceito de Joshi.

Dependências Cross-serial editar

O termo dependências Cross-serial refere-se a uma específica ordenação de padrões de palavras, em particular, ao padrão verb-argument observado nas cláusulas subordinadas em alemão[1] e suíço-alemão.[2] Esses são os vários padrões que podem ser usados para se argumentar contra a liberdade de contexto da linguagem natural; exigindo, portanto, que gramáticas moderadamente sensíveis ao contexto modelem dependências cross-serial, que significa que essas gramáticas devem ser mais poderosas que gramáticas livre de contexto.

Kallmeyer[13] relaciona a capacidade de modelar dependencias corss-serial com a capacidade de gerar a linguagem-cópia

 

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

Crescimento constante editar

A linguagem formal é de crescimento constante se cada cadeia na linguagem é mais longa do que as próximas cadeias mais curtas por no máximo um (linguagem específica) constante. Linguagens que violam essa propriedade frequentemente são consideradas ser além da capacidade humanda, embora alguns autores argumentem que certos fenômenos em linguagem natural mostram um crescimento que não pode ser limitado por uma constante. [14] Jens Michaelis e Marcus Kracht.

A maioria das descrições formais de gramáticas moderadamente sensível ao contexto (em particular, LCFRS/MCFG) atualmente satisfazem uma propriedade mais forte que um crescimento constante, chamada semi linearidade.[7] Uma linguagem é semi linear se sua imagem sob Parikh-mapping (O mapeamento que ‘desconsidera’ a posição relativa de que símbolos em uma cadeia, efetivamente tratando isso como um conjunto de palavras) é uma linguagem regular. Toda linguagem semi linear é de crescimento constante, mas não toda linguagem que é de crescimento constante é semi linear.[11]

Análise Polinomial editar

Uma gramática formal é dita ter análise polinomial se a pertinência do problema pode ser resolvida em tempo polinomial. Esse é o problema de decidir, dado uma gramatica G escrita no formalismo e uma cadeia w, se w é gerada por G. A complexidade de tempo desse problema é medido em termos do tamanho combinado de  G e w.

Sob o conceito de sensibilidade ao contexto moderada como propriedade de classes de linguagem, análise polinomial refere-se ao problema de pertencimento da linguagem. Esse é o problema de decidir, para uma linguagem L, se uma dada cadeia w, pertence a  L. A complexidade de tempo deste problema é medido em termos do comprimento de w, ignora a questão de como L é descrita.

Note que ambos pontos de vista de análise polinomial são idealizações no senso prático que são não apenas interessadas na questão de se uma sentença é ou não gerada por uma gramática, mas também na estrutura sintática que a gramática aplica na sentença.

Formalismos editar

Ao passar dos anos, um grande número de gramáticas formais que satisfazem algumas ou todas as características descritas por Joshi têm sido introduzidas. Várias delas tem alternativas, definições baseada em autômatos que não são discutidas neste artigo; por exemplo, linguagens geradas por gramáticas de árvore-adjacente podem ser definidas por Autômato com pilha embutido

Formalismos equivalentes a Gramáticas de Árvore-Adjacente (TAG) editar

Formalismos equivalentes a LCFRS/MCFG gerais editar

Formalismos equivalentes a LCFRS/MCFG bem aninhadas editar

  • Macro gramáticas não-duplicantes (tradução livre de Non-duplicating macro grammars)[20]
  • Gramáticas livres de contexto acopladas (tradução livrve de Coupled context-free grammars, CCFG em siglas)[21]
  • Gramáticas livres de contexto generalizadas bem aninhadas[12]
  • Gramáticas livre de contexto multiplas bem aninhadas[10]

Relacionamento entre os formalismos editar

LCFRS/MCFG forma uma hierarquia bidimensional de poder gerador com respeito a dois parâmetros específicos de gramáticas chamados fan=out e rank.[22] Mais precisamente, as linguagens geradas por LCFRS/MCFGcom fan-out f ≥ 1 e rank r ≥ 3 são devidamente incluídos na classe de linguagens geradas por LCFRS/MCFG com rank r + 1 e fan-out f, assim como a classe de linguagens geradas por LCFRS/MCFG with rank r e fan-out f + 1. Na presença de "bem-aninhamento" (tradução livre de well-nestedness), essa hierarquia colapsa para uma hierarquia unidimensional com respeito ao fan-out;Isso porque toda LCFRS/MCFG bem aninhada pode ser transformada em uma LCFRS/MCFG bem aninhada equivalente com o mesmo fan-out e rank 2.[10][12] Na hierarquia da LCFRS/MCFG, as linguagens livres de contexto podem ser caracterizadas por gramáticas com fan-out 1; Por esse fan-out não há diferença entre gramáticas generalizadas e bem aninhadas. Os formalismos equivalentes às gramáticas de árvore-adjacente podem ser caracterizados como LCFRS/MCFG bem aninhados de fan-out 2.

Veja também editar

Referências editar

  1. ↑ a b Riny Huybregts. The Weak Inadequacy of Context-Free Phrase Structure Grammars. In Ger de Haan, Mieke Trommelen, and Wim Zonneveld, editors, Van periferie naar kern, pages 81–99. Foris, Dordrecht, The Netherlands, 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: How Much Context-Sensitivity Is Required to Provide Reasonable Structural Descriptions?. In David R. Dowty, Lauri Karttunen, and Arnold M. Zwicky, editors, Natural Language Parsing, pages 206–250. Cambridge University Press, 1985.
  4. ↑ David J. Weir, K. Vijay-Shanker, and Aravind K. Joshi. The Relationship Between Tree Adjoining Grammars and Head Grammars. In Proceedings of the 24th Annual Meeting of the Association for Computational Linguistics (ACL), pages 67–74, New York, USA, 1986.
  5. ↑ K. Vijay-Shanker. A Study of Tree Adjoining Grammars. Ph.D. thesis, University of Pennsylvania, Philadelphia, USA, 1987.
  6. ↑ a b David J. Weir and Aravind K. Joshi. Combinatory Categorial Grammars: Generative Power and Relationship to Linear Context-Free Rewriting Systems. In Proceedings of the 26th Annual Meeting of the Association for Computational Linguistics (ACL), pages 278–285, Buffalo, USA, 1988.
  7. ↑ a b c d K. Vijay-Shanker, David J. Weir, and Aravind K. Joshi. Characterizing Structural Descriptions Produced by Various Grammatical Formalisms. In Proceedings of the 25th Annual Meeting of the Association for Computational Linguistics (ACL), pages 104–111, Stanford, CA, USA, 1987.
  8. ↑ a b David J. Weir. Characterizing Mildly Context-Sensitive Grammar Formalisms. Ph.D. thesis, University of Pennsylvania, Philadelphia, USA, 1988.
  9. ↑ a b Hiroyuki Seki, Takashi Matsumura, Mamoru Fujii, and Tadao Kasami. On Multiple Context-Free Grammars. Theoretical Computer Science, 88(2):191–229, 1991.
  10. ↑ a b c d Makoto Kanazawa. The Pumping Lemma for Well-Nested Multiple Context-Free Languages. In Developments in Language Theory. 13th International Conference, DLT 2009, Stuttgart, Germany, June 30–July 3, 2009. Proceedings, volume 5583 of Lecture Notes in Computer Science, pages 312–325, 2009.
  11. ↑ a b Laura Kallmeyer. On Mildly Context-Sensitive Non-Linear Rewriting. Research on Language and Computation, 8(4):341–363, 2010.
  12. ↑ a b c Carlos Gómez-Rodríguez, Marco Kuhlmann, and Giorgio Satta. Efficient Parsing of Well-Nested Linear Context-Free Rewriting Systems. In Proceedings of Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics (NAACL), pages 276–284, Los Angeles, USA, 2010.
  13. ↑ a b Laura Kallmeyer. Parsing Beyond Context-Free Grammars. Springer, 2010.
  14. ↑ Jens Michaelis and Marcus Kracht. Semilinearity as a Syntactic Invariant. In Logical Aspects of Computational Linguistics. First International Conference, LACL 1996, Nancy, France, September 23–25, 1996. Selected Papers, volume 1328 of Lecture Notes in Computer Science, pages 329–345. Springer, 1997.
  15. ↑ Carl J. Pollard. Generalized Phrase Structure Grammars, Head Grammars, and Natural Language. Ph.D. thesis, Stanford University, 1984.
  16. ↑ Kelly Roach. Formal Properties of Head Grammars. In Alexis Manaster-Ramer, editor, Mathematics of Language, pages 293–347. John Benjamins, 1987.
  17. ↑ Gerald Gazdar. Applicability of Indexed Grammars to Natural Language. In Uwe Reyle and Christian Rohrer, editors, Natural Language Parsing and Linguistic Theories, pages 69–94. D. Reidel, 1987.
  18. ↑ Jens Michaelis. Derivational Minimalism Is Mildly Context-Sensitive. In Logical Aspects of Computational Linguistics, Third International Conference, LACL 1998, Grenoble, France, December 14–16, 1998, Selected Papers, volume 2014 of Lecture Notes in Computer Science, pages 179–198. Springer, 1998.
  19. ↑ Pierre Boullier. Range Concatenation Grammars. In Harry C. Bunt, John Carroll, and Giorgio Satta, editors, New Developments in Parsing Technology, volume 23 of Text, Speech and Language Technology, pages 269–289. Kluwer Academic Publishers, 2004.
  20. ↑ Michael J. Fischer. Grammars with Macro-Like Productions. In Ninth Annual Symposium on Switching and Automata Theory, pages 131–142, Schenectady, NY, USA, 1968.
  21. ↑ Günter Hotz and Gisela Pitsch. On Parsing Coupled-Context-Free Languages. Theoretical Computer Science, 161(1–2):205–233, 1996.
  22. ↑ Owen Rambow and Giorgio Satta. A Two-Dimensional Hierarchy for Parallel Rewriting Systems. Technical Report IRCS-94-02, University of Pennsylvania, Philadelphia, USA, 1994.

Obtida de "https://pt.wikipedia.org/w/index.php?title=Gramática_moderadamente_sensível_ao_contexto&oldid=66448761"