Grammatica sensibile al contesto
Da Wikipedia, l'enciclopedia libera.
Una grammatica sensibile al contesto, o context-sensitive, o di Tipo 1 nella gerarchia di Chomsky, è definita sulla seguente regola di produzione:
cioè, per ogni produzione di β, questa non può essere più piccola di α, cioè o ha la stessa cardinalità o è più grande.
Una grammatica sensibile al contesto è quindi una grammatica formale G = (N, Σ, P, S) tale che tutte le regole di produzione in P sono nella forma
- αAβ → αγβ
con A in N (i.e., A è un simbolo nonterminale) e α e β in (N U Σ)* (i.e., α e β stringhe di simboli non terminali e terminali) e γ in (N U Σ)+ (i.e., γ una stringa non vuota di terminali e non terminali). Le stringhe α e β possono essere vuote, ma la γ non deve essere vuota. La regola di produzione 
è permessa se S non appare nel lato destro delle regole di produzione.
Il nome sensibile al contesto è spiegato dall' α e β che formano il contesto di A e determinano se A può essere rimpiazzata o no con γ. In una grammatica libera dal contesto, invece, il contesto di un nonterminale non è preso in cosiderazione. Un linguaggio formale che può essere descritto da una grammatica sensibile al contesto è chiamato linguaggio sensibile al contesto.
Il concetto di grammatica sensibile al contesto fu introdotto da Noam Chomsky negli anni 50 come modo per descrivere la sintassi di un linguaggio naturale dove si trova spesso il caso che una parola possa o non possa essere appropriata in una certa posizione a seconda del contesto.
Indice |
[modifica] Definizione alternativa
Un'altra definizione di grammatica sensibile al contesto la definisce come una grammatica formale con la restrizione che per tutte le regole di produzione α -> β in P si ha che | α | ≤ | β | dove | α | è la lunghezza di α. Questa grammatica è chiamata anche monotonica o grammatica che non contrae poiché nessuna delle regole decrementa la grandezza della stringa che viene riscritta.
Mentre le grammatiche monotoniche sono diverse da quelle sensibili al contesto, le due sono quasi equivalenti nel senso che definiscono la stessa classe di linguaggi (eccetto che le grammatiche monotoniche non possono generare nessun linguaggio che contenga la stringa vuota ε). Ma se un linguaggio formale L può essere descritto da una grammatica della prima definizione allora c'è una grammatica monotonica che descrive L - {ε}, e vice versa.
[modifica] Esempio
Una semplice grammatica monotonica è
- S → abc | aSBc
- cB → Bc
- bB → bb
dove | è utilizzato per separare diverse opzioni dello stesso non-terminale. Questa grammatica genera il linguaggio 
, che non è libero dal contesto. Le grammatiche sensibili al contesto possono superare i limiti posti dalle grammatiche libere dal contesto: esiste per esempio una grammatica sensibile al contesto per il linguaggio 
, ma le regole di produzione sono molto più complesse di quelle descritte poco sopra.
[modifica] Forme normali
Ogni grammatica sensibile al contesto che non genera la stringa vuota può essere trasformata in una equivalente grammatica in forma normale di Kuroda. Per equivalente si intende che generano lo stesso linguaggio.
[modifica] Proprietà computazionali
Il problema della decisione che richiede se una certa stringa s appartenga al linguaggio di una certa grammatica libera dal contesto G, è PSPACE-complete. Certamente, ci sono anche alcune grammatiche sensibili al contesto il cui problema di riconoscimento della grammatica è PSPACE-complete.
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. | |||
