Grammatica dipendente dal contesto

Una grammatica dipendente dal contesto (o contestuale, context-sensitive, o anche sensibile al contesto) è una grammatica formale nella quale la forma delle produzioni ne vincola l'applicazione solo a determinati contesti. Le grammatiche dipendenti dal contesto sono più generali e potenti di quelle libere dal contesto, e sono a loro volta meno generali delle grammatiche a struttura di frase. I linguaggi descritti dalle grammatiche dipendenti dal contesto possono essere riconosciuti dagli automi lineari.

Il concetto di grammatica dipendente dal contesto fu introdotto da Noam Chomsky negli anni cinquanta 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. Nella gerarchia di Chomsky le grammatiche dipendenti dal contesto sono dette di Tipo 1. Un linguaggio formale che può essere descritto da una grammatica dipendente dal contesto è chiamato linguaggio dipendente dal contesto (o di Tipo 1).

Definizione formale

Una grammatica dipendente dal contesto è 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 non terminale) 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 $\alpha$ e $\beta$ possono essere vuote, ma la $\gamma$ non deve essere vuota. La regola di produzione S → ε è permessa se S non appare nel lato destro di alcuna regola di produzione.

Il nome dipendente dal 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 non terminale non è preso in considerazione.

Definizione alternativa

Una classe più generale è quella delle grammatiche monotòne. Una grammatica è monotona se ogni regola di produzione è della forma

α → β   con | α | ≤ | β |

dove | α | è la lunghezza di α (cioè il numero dei simboli di α); è anche permessa la regola di produzione S → ε, se S non appare nel lato destro di alcuna regola di produzione.

Una grammatica del genere è detta monotona perché nessuna delle regole decrementa la grandezza della stringa che viene riscritta.

È facile rendersi conto che ogni grammatica dipendente dal contesto è monotona, ma esistono grammatiche monotone che non sono dipendenti dal contesto (un esempio segue tra poco). Ciò nonostante, la classe dei linguaggi descrivibili dalle grammatiche dipendenti dal contesto coincide con quella dei linguaggi descrivibili dalle grammatiche monotone. Se un linguaggio formale L può essere descritto da una grammatica monotona, allora è possibile costruire una grammatica dipendente dal contesto che descrive L.

Esempio

Una semplice grammatica monotona è

S → abc | aSBc

cB → Bc

bB → bb

dove | è utilizzato per separare diverse opzioni dello stesso non-terminale. Questa grammatica genera il linguaggio $\{a^{n}b^{n}c^{n}:n\geq 1\}$, che non è libero dal contesto. Questa grammatica non è dipendente dal contesto, perché nella produzione della seconda linea la parte destra non inizia con il terminale c col quale inizia invece la sua parte sinistra. Una grammatica dipendente dal contesto per lo stesso linguaggio è

1. $S\rightarrow aSBC$
2. $S\rightarrow aBC$
3. $CB\rightarrow HB$
4. $HB\rightarrow HC$
5. $HC\rightarrow BC$
6. $aB\rightarrow ab$
7. $bB\rightarrow bb$
8. $bC\rightarrow bc$
9. $cC\rightarrow cc$

Grammatiche più complesse possono essere date per altri linguaggi dipendenti dal contesto, come per esempio $\{a^{n}b^{n}c^{n}d^{n}:n\geq 1\}$.

Forme normali

Ogni grammatica dipendente dal 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.

Proprietà computazionali

Il problema della decisione che richiede se una certa stringa s appartenga al linguaggio di una certa grammatica non libera dal contesto G, è PSPACE-complete. Certamente, ci sono anche alcune grammatiche dipendenti dal contesto il cui problema di riconoscimento della grammatica è PSPACE-complete.

Bibliografia

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

Voci correlate

• Gerarchia di Chomsky