Linguaggio sensibile al contesto
Da Wikipedia, l'enciclopedia libera.
Un linguaggio sensibile al contesto è un linguaggio formale che può essere definito da una grammatica sensibile al contesto. È una dei quattro tipi di grammatica della Gerarchia di Chomsky. È la meno utilizzata, sia in teoria che in pratica.
[modifica] Proprietà computazionali
Computazionalmente un linguaggio sensibile al contesto è equivalente ad un automa lineare limitato . Questa è una 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. È ampiamente sospettato che non siano uguali.
[modifica] Esempi
Un esempio di linguaggio sensibile al contesto che non è context-free è L = { ap : p è un numero primo }. Il modo più semplice per dimostrare ciò è tramite un automa lineare limitato.
[modifica] 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.
Vedere anche: Gerarchia di Chomsky
| Teoria degli automi: linguaggi formali e grammatiche formali | |||
|---|---|---|---|
| gerarchia di Chomsky |
Grammatiche | Linguaggi | automa minimo |
| Tipo-0 | (illimitato) | Ricorsivamente enumerabile | Macchina di Turing |
| (illimitato) | Ricorsivo | Decider | |
| Tipo-1 | Sensibile al contesto | Sensibile al contesto | Lineare-limitato |
| Tipo-2 | Libero dal contesto | Libero dal contesto | Automa a pila |
| Tipo-3 | Lineare (o Regolare) | Lineare (o Regolare) | A stati finiti |
| Ciascuna categoria di linguaggio o grammatica è un sottoinsieme del proprio sovrainsieme di categoria direttamente sottostante. | |||
