Gramática sensível ao contexto

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

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[editar | editar código-fonte]

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 AN(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[editar | editar código-fonte]

  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 \ge 1 \} , e outras linguagens ainda com mais letras.

  • A gramática seguinte gera a linguagem de cópia não-livre do contexto, C = \{ x x | 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[editar | editar código-fonte]

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[editar | editar código-fonte]

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.

Referências

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

Ver também[editar | editar código-fonte]

Ligações externas[editar | editar código-fonte]

Teoria de autômatos: linguagem formal e gramática formal
Hierarquia
Chomsky
Gramática Linguagem Reconhecedor
Tipo-0 Irrestrita Recursivamente enumerável Máquina de Turing
-- -- Recursiva Máquina de Turing que sempre para
Tipo-1 Sensível ao contexto Sensível ao contexto Autômato linearmente limitado
Tipo-2 Livre de contexto Livre de contexto Autômato com pilha
Tipo-3 Regular Regular Autômato finito