Linguagem sensível ao contexto – Wikipédia, a enciclopédia livre

Na Ciência da computação teórica, a 'linguagem sensível ao contexto' é uma linguagem formal que pode ser definida por uma Gramática sensível ao contexto. Esse é um dos quatro tipos de gramáticas na hierarquia de Chomsky.

Computacionalmente, uma linguagem sensível ao contexto é equivalente a uma máquina de Turing não determinística linearmente limitada, também chamado de autômato linearmente limitado. Ela é uma máquina de Turing não determinística com uma fita de apenas kn 'células', onde 'n' é o tamanho da entrada e 'k' é uma constante associada com a máquina. Isto significa que toda linguagem formal que pode ser decidida por uma máquina desse tipo é uma linguagem sensível ao contexto, e cada linguagem sensível ao contexto pode ser decidida por uma máquina desse tipo.

Este conjunto de linguagens também é conhecido como 'NLINSPACE' ou 'NSPACE' (O '(' 'n' ')), porque eles podem ser aceitos usando o espaço linear em uma máquina de Turing não determinística.^[1] A classe LINSPACE (ou DSPACE(O(n))) é definida da mesma forma, exceto por usar uma máquina de Turing determinística. Claramente LINSPACE é um subconjunto de NLINSPACE, mas não se sabe se LINSPACE=NLINSPACE.^[2]

Uma das mais simples linguagens sensíveis ao contexto, mas que não é livre de contexto é ${\displaystyle L=\{a^{n}b^{n}c^{n}:n\geq 1\}}$: A linguagem de todas as cadeias consistindo em n ocorrências do símbolo "a", e n "b"'s, e n "c"'s (abc, aabbcc, aaabbbccc, etc.). Um superconjunto dessa linguagem, chamada de linguagem de Bach,^[3] é definido como o conjunto de todas as cadeias onde "a", "b" e "c" (ou qualquer outro conjunto de símbolos) ocorrem com a mesma frequência (aabccb, baabcaccb, etc.) e isso também é sensível ao contexto.^[4][5]

Outro exemplo de linguagem sensível ao contexto que não é livre de contexto é L = { a^p : p é um número primo }. Podemos demonstrar que L é sensível ao contexto construindo um autômato limitado linearmente que aceita L. Podemos demonstrar facilmente que a linguagem não é nem regular e nem livre de contexto aplicando os respectivos lemas de bombeamento para cada classe de linguagem para L. Um exemplo de linguagem recursiva que não é sensível ao contexto é qualquer linguagem recursiva cuja decisão é um problema EXPSPACE-HARD, como exemplo o conjunto de pares de expressões regulares são equivalentes com a exponenciação.

• A união, interseção, concatenação e operação estrela/fecho de kleene de duas as linguagens sensíveis ao contexto é uma linguagem sensível ao contexto.^[6]
• O complemento de uma linguagem sensível ao contexto é em si sensível ao contexto.^[7]
• Toda gramática livre de contexto que não contém a String vazia é sensível ao contexto.^[8]
• A composição de uma cadeia em uma linguagem definida arbitrariamente por uma gramática sensível ao contexto, ou por uma gramática sensível ao contexto determinística arbitrária, é um problema PSPACE-completo.

• Autômato linearmente limitado
• Hierarquia de Chomsky

• Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.