Gramática sensível ao contexto

Em Teoria da computação uma gramática sensível ao contexto (GSC), também conhecida como Tipo 1 da Hierarquia de Chomsky, é uma gramática formal em que os lados esquerdo e direito de qualquer regra de produção podem ser cercados por um contexto de símbolo terminal e símbolo não-terminal. Gramáticas sensíveis ao contexto são mais gerais do que as gramáticas livres de contexto mas ainda ordenadas o suficiente para serem verificadas por um autômato linearmente limitado.

O conceito de gramática sensível ao contexto foi introduzido por Noam Chomsky na década de 1950 como uma maneira de descrever a sintaxe de linguagem natural, em que, de fato, é frequentemente o motivo de uma palavra poder ou não ser apropriada em um determinado lugar, dependendo do contexto. A linguagem formal, que pode ser descrita por uma gramática sensível ao contexto, é chamada de linguagem sensível ao contexto.

Definição formal

A gramática formal G= (N, Σ,P,S) (equivalente a G= (V,T,P,S), basta que V(ariável) não-Terminal seja substituída por N e T(erminal) passa a ser Σ) é sensível ao contexto se todas as regras em P são da forma

αAβ → αγβ

em que A∈N(isto é, A é um único não-terminal), α,β ∈ (N U Σ)* (ou seja, α e β são sequências de não-terminais e símbolo terminal) e γ ∈ (N U Σ)⁺ (isto é, γ é uma sequência não vazia de não-terminais e terminais).

Algumas definições ainda acrescentam que para qualquer regra de produção da forma u → v de uma gramática sensível ao contexto, deve ser verdade que |u| ≤ |v|. Aqui |u| e |v| denotam o comprimento das cadeias, respectivamente.

Além disso, uma regra da forma

S → λ desde que S não apareça no lado direito de qualquer regra

em que λ representa a cadeia vazia é permitido. A adição de uma cadeia vazia permite a afirmação de que as linguagens sensíveis ao contexto são um superconjunto adequado das linguagens livre do contexto, ao invés de ter que fazer uma declaração mais fraca de que todas as gramáticas livres de contexto, sem produções → λ são também gramáticas sensíveis ao contexto.

O nome sensível ao contexto é explicado pelo α e β que formam o contexto de A e determinar se A pode ser substituído por γ ou não. Isto é diferente de uma gramática livre de contexto, em que o contexto de um não-terminal não é levado em consideração. (Na verdade, todas as produções de uma gramática livre de contexto é da forma V → w, em que V é um único símbolo não-terminal, e w é uma cadeia de terminais e/ou não-terminais (w pode ser vazio)).

Se a possibilidade de adicionar a cadeia vazia para uma linguagem, é adicionada às cadeias reconhecidas pelas gramáticas não-contratuais (que nunca podem incluir a cadeia vazia), então as linguagens, nessas duas definições, são idênticas.

Exemplos

• Essa gramática gera a linguagem não-livre do contexto canônica $\{a^{n}b^{n}c^{n}|n\geq 1\}$:

1. $S\rightarrow aSBC$
2. $S\rightarrow aBC$
3. $CB\rightarrow HB$
4. $HB\rightarrow HC$
5. $HC\rightarrow BC$
6. $aB\rightarrow ab$
7. $bB\rightarrow bb$
8. $bC\rightarrow bc$
9. $cC\rightarrow cc$

A derivação para aaabbbccc é:

$S$

$\Rightarrow _{1}aSBC$

$\Rightarrow _{1}a{\boldsymbol {aSBC}}BC$

$\Rightarrow _{2}aa{\boldsymbol {aBC}}BCBC$

$\Rightarrow _{3}aaaB{\boldsymbol {HB}}CBC$

$\Rightarrow _{4}aaaB{\boldsymbol {HC}}CBC$

$\Rightarrow _{5}aaaB{\boldsymbol {BC}}CBC$

$\Rightarrow _{3}aaaBBC{\boldsymbol {HB}}C$

$\Rightarrow _{4}aaaBBC{\boldsymbol {HC}}C$

$\Rightarrow _{5}aaaBBC{\boldsymbol {BC}}C$

$\Rightarrow _{3}aaaBB{\boldsymbol {HB}}CC$

$\Rightarrow _{4}aaaBB{\boldsymbol {HC}}CC$

$\Rightarrow _{5}aaaBB{\boldsymbol {BC}}CC$

$\Rightarrow _{6}aa{\boldsymbol {ab}}BBCCC$

$\Rightarrow _{7}aaa{\boldsymbol {bb}}BCCC$

$\Rightarrow _{7}aaab{\boldsymbol {bb}}CCC$

$\Rightarrow _{8}aaabb{\boldsymbol {bc}}CC$

$\Rightarrow _{9}aaabbb{\boldsymbol {cc}}C$

$\Rightarrow _{9}aaabbbc{\boldsymbol {cc}}$

Gramáticas mais complicadas podem ser usadas para verificar $\{a^{n}b^{n}c^{n}d^{n}|n\geq 1\}$, e outras linguagens ainda com mais letras.

• A gramática seguinte gera a linguagem de cópia não-livre do contexto, $C=\{xx|x\in \{a,b\}^{*}\}$:

1. $S\rightarrow aAS|bBS|T$
2. $Aa\rightarrow aA$
3. $Ba\rightarrow aB$
4. $Ab\rightarrow bA$
5. $Bb\rightarrow bB$
6. $BT\rightarrow Tb$
7. $AT\rightarrow Ta$
8. $T\rightarrow \epsilon$

A derivação para abab é:

$S$

$\Rightarrow _{1}aAS$

$\Rightarrow _{1}aA{\boldsymbol {bBS}}$

$\Rightarrow _{1}aAbB{\boldsymbol {T}}$

$\Rightarrow _{4}a{\boldsymbol {bA}}BT$

$\Rightarrow _{6}abA{\boldsymbol {Tb}}$

$\Rightarrow _{7}ab{\boldsymbol {Ta}}b$

$\Rightarrow _{8}abab$

Formas Normais

Toda gramática sensível ao contexto que não gera a cadeia vazia pode ser transformada em uma equivalente na forma normal de Kuroda. "Equivalente" aqui significa que as duas gramáticas geram a mesma linguagem. A forma normal não vai, em geral, ser sensível ao contexto, mas vai ser uma gramática não-contratual.

Propriedades e usos computacionais

O problema da decisão que pergunta se uma certa cadeia s pertence à linguagem de uma certa gramática sensível ao contexto G, é PSPACE-completo. Existem mesmo algumas gramáticas sensíveis ao contexto, cujo problema de reconhecimento fixo de gramática é PSPACE-completo.

O problema da vacuidade para gramáticas sensíveis ao contexto (dada a gramática sensível ao contexto G, é $L(G)=\emptyset$ ?) é indecidível.

Tem sido demonstrado que quase todas as linguagens naturais podem, em geral, serem caracterizadas por gramáticas sensíveis ao contexto, mas toda a classe de GSC parece ser muito maior do que as linguagens naturais . Pior ainda, pois o problema da decisão para GSC é PSPACE-completo, que os torna totalmente inviáveis para o uso prático, como um algoritmo de tempo polinomial para um problema PSPACE-total implicaria P=NP. Investigações em andamento sobre linguística computacional têm se centrado na formulação de outras classes de linguagens que são "levemente sensíveis ao contexto" cujos problemas de decisão sejam factíveis, assim como as gramáticas de árvores-adjuntas, gramáticas de categoria combinatória, linguagens livre de contexto acopladas, e sistemas lineares reescrevíveis livres de contexto. As linguagens geradas por esses formalismos, estão entre as linguagens livres de contexto, e as sensíveis ao contexto.

Ver também

• Hierarquia de Chomsky

Referências

• Introduction to Languages and the Theory of Computation by John C. Martin McGraw Hill 1996 (2nd edition)

Ligações externas

• «Earley Parsing for Context-Sensitive Grammars» (PDF)