# 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

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. 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’. 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. Seguido por 2 resultados equivalentes, para Gramática indexada (LIG, do inglês linear indexed grammar) e gramática categorial combinatória (CGC, do inglês combinatory categorial grammar), 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).
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).
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, e que há linguagens que tem propriedades características de serem moderadadamente sensiveis ao contexto mas não são geradas por LCFRS/MCFG.
Nos últimos anos, tem crescido o interesse na classe restrita de gramáticas LCFRS/MCFG bem aninhadas (tradução livre de well-nested), 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

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, uma classe de gramáticas moderadamente sensivél ao contexto deve ter as seguintes propriedades:
* limitadas dependências cross-serial
* crescimento constante
* 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:
Outros autores tem proposto definições alternativas da sensibilidade ao contexto moderada, alguns têm definições formais. Por exemplo, Laura Kallmeyer 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

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 e suíço-alemão. 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 relaciona a capacidade de modelar dependencias corss-serial com a capacidade de gerar a linguagem-cópia
${\mathit {COPY}}=\{\,ww\mid w\in \{a,b\}^{*}\,\}$
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

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. 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. 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.

### Análise Polinomial

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

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)

* Gramática de Árvore-Adjacente (TAG)
* Gramática de Cabeça (HG)
* Gramática indexada (LIG)
* gramática categorial combinatória (CCG)
* Bem-aninhado (tradução livre de Well-nested) LCFRS/MCFG de fan-out 2

### Formalismos equivalentes a LCFRS/MCFG gerais

* Gramáticas Livre de Contexto Generalizadas (LCFRS)
* Gramáticas livre de contexto múltiplas (MCFG)
* Gramáticas de árvore-adjacente multicomponente(MCTAG)
* Gramáticas minimalistas (MG, do inglês Minimalist grammar)
* Simples (linear, não apaga símbolos, não-combinatória), positiva Gramática de Concatenação de Intervalo (RCG)

### Formalismos equivalentes a LCFRS/MCFG bem aninhadas

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

### Relacionamento entre os formalismos

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. 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. 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

* Gramática de árvore-adjacente
* Gramática Livre de Contexto
* Gramática de Concatenação de Intervalo
* Hierarquia de Weir
* Autômato com pilha embutido