Linguaggio dipendente dal contesto

Un linguaggio dipendente dal contesto (o anche sensibile al contesto, vincolato al contesto, o contestuale) è un linguaggio formale che può essere definito da una grammatica dipendente dal contesto. È una dei quattro tipi di grammatica della Gerarchia di Chomsky. È la meno utilizzata, sia in teoria che in pratica.

Proprietà computazionali modifica

Computazionalmente un linguaggio dipendente dal contesto è equivalente ad un automa lineare limitato . Questa è una macchina di Turing non-deterministica con un nastro di sole kn celle, dove 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 dipendente dal contesto e che ogni linguaggio dipendente dal 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. È ampiamente sospettato che non siano uguali.

Esempi modifica

Un esempio di linguaggio dipendente dal contesto che non è libero dal contesto è L = { ap : p è un numero primo }. Il modo più semplice per dimostrare che si tratta di un linguaggio dipendente dal contesto è usare un automa lineare limitato. Una dimostrazione che L non è libero dal contesto può essere ottenuta mediante il pumping lemma.

Proprietà dei linguaggi dipendenti dal contesto modifica

  • L'unione, l'intersezione e la concatenazione di due linguaggi dipendenti dal contesto è dipendente dal contesto.
  • Il complemento di un linguaggio dipendente dal contesto è esso stesso dipendente dal contesto.
  • Ogni linguaggio libero dal contesto fa parte anche dell'insieme dei linguaggi dipendenti dal contesto.

Bibliografia modifica

  • Giorgio Ausiello, Fabrizio D'Amore, Giorgio Gambosi, Linguaggi modelli complessità, Milano, Franco Angeli Editore, 2003, ISBN 88-464-4470-1.

Voci correlate modifica

Teoria degli automi: linguaggi formali e grammatiche formali
Gerarchia di Chomsky Grammatica formale Linguaggio Automa minimo
Tipo-0 (illimitato) Ricorsivamente enumerabile Macchina di Turing
(illimitato) Ricorsivo Decider
Tipo-1 Dipendente dal contesto Dipendente dal contesto Automa lineare
Tipo-2 Libera dal contesto Libero dal contesto Automa a pila ND
Tipo-3 Regolare Regolare A stati finiti
Ciascuna categoria di linguaggio o grammatica è un sottoinsieme proprio della categoria immediatamente sovrastante.