Gramática sensível ao contexto
A Gramática Sensível ao Contexto (GSC), ou Tipo 1 da Hierarquia de Chomsky, é uma gramática formal onde as regras de produção podem ter um contexto de símbolos terminais e não-terminais. Mais poderosas que as gramáticas livres de contexto, as GSCs são reconhecidas por autômatos linearmente limitados, sendo fundamentais na teoria da computação.
Pontos-chave
- GSCs são o Tipo 1 da Hierarquia de Chomsky e mais gerais que as gramáticas livres de contexto.
- Suas regras de produção permitem contexto de símbolos terminais e não-terminais.
- São verificadas por autômatos linearmente limitados.
- O problema de decisão para GSCs é PSPACE-completo, tornando-as inviáveis para uso prático direto.
- Linguagens naturais podem ser caracterizadas por GSCs, mas a classe é muito ampla.
Uma gramática formal G = (N, Σ, P, S) é sensível ao contexto se todas as regras de produção em P seguem o formato αAβ → αγβ, onde A é um único não-terminal, α e β são sequências (possivelmente vazias) de não-terminais e terminais, e γ é uma sequência não vazia de não-terminais e terminais. Algumas definições adicionam a condição de que o comprimento da cadeia do lado esquerdo (u) deve ser menor ou igual ao comprimento da cadeia do lado direito (v), ou seja, |u| ≤ |v|. A permissão da cadeia vazia (λ) como produção (S → λ) é crucial para que as linguagens sensíveis ao contexto sejam um superconjunto adequado das linguagens livres de contexto.
Gramáticas Sensíveis ao Contexto são capazes de descrever linguagens mais complexas, como { aⁿbⁿcⁿdⁿ | n ≥ 1 }, que não podem ser geradas por gramáticas livres de contexto. Elas podem ser estendidas para verificar padrões com um número maior de letras, demonstrando sua capacidade de lidar com dependências contextuais mais intrincadas.
Qualquer gramática sensível ao contexto que não gere a cadeia vazia pode ser convertida para uma forma equivalente conhecida como Forma Normal de Kuroda. Embora a forma normal resultante não seja necessariamente sensível ao contexto, ela será uma gramática não-contratual, o que significa que as duas gramáticas (a original e a na forma normal) geram a mesma linguagem.
O problema de decidir se uma cadeia pertence à linguagem de uma GSC é PSPACE-completo, o que significa que é computacionalmente caro. O problema da vacuidade (verificar se uma GSC gera uma linguagem vazia) é indecidível. Embora as linguagens naturais possam ser caracterizadas por GSCs, a classe completa é muito vasta e os problemas de decisão PSPACE-completos as tornam impraticáveis para uso direto em algoritmos, pois implicaria P=NP. Por isso, a linguística computacional foca em classes de linguagens 'levemente sensíveis ao contexto' com problemas de decisão mais factíveis, como gramáticas de árvores-adjuntas e gramáticas de categoria combinatória, que se situam entre as linguagens livres de contexto e as sensíveis ao contexto.
