Un linguaggio sensibile al contesto è un linguaggio formale che può essere definito da una grammatica sensibile al contesto. E' una dei quattro tipi di grammatica nella Gerarchia di Chomsky. Uno dei quattro, è il meno utilizzato, sia in teoria che in pratica.

Proprietà computationali

Computazionalmente un linguaggio sensibile al contesto è equivalente ad un automa lineare limitato . Questa è macchina di Turing non-deterministica con un nastro di sole kn celle, deve n è la grandezza dell'input e k è una costante che dipende dalla macchina. Questo significa che ogni linguaggio formale che può essere deciso da questa macchina è un linguaggio sensibile al contesto e che ogni linguaggio sensibile al contesto può essere deciso da una macchina del genere.

Questo insieme di linguaggi è conosciuto anche come NLIN-SPACE, poichè possono essere accettati utilizzando uno spazio lineare su una macchina di Turing non deterministica. La classe LIN-SPACE è definita nello stesso modo, eccetto per il fatto che utilizza una macchina di Turing deterministica. Chiaramente LIN-SPACE è un sottoinsieme di un NLIN-SPACE, ma non si sa se LIN-SPACE=NLIN-SPACE. E' ampliamente sospettato che non siano uguali.

Esempi

Un esempio di linguaggio sensibile al contesto che non è context-free è L = { a^p : p è un numero primo }. Il modo più semplice per dimostrare ciò è tramite un automa lineare limitato.

Proprietà dei linguaggi sensibili al contesto

• L'unione, l' intersezione e la concatenazione di due linguaggi sensibili al contesto è sensibile al contesto.
• Il complemento di un linguaggio sensibile al contesto è esso stesso sensibile al contesto.
• Ogni linguaggio context-free è sensibile al contesto.

Linguaggi formali

Kontextový jazyk | Kontextsensitive Sprache | Context-sensitive language | 文脈依存言語 | Język kontekstowy