Quando si studiano automi e grammatiche si ha l'impressione di accumulare modelli diversi: DFA, automi a pila, macchine di Turing, grammatiche regolari, libere dal contesto e così via. La gerarchia di Chomsky mette ordine in questo panorama. Classifica le grammatiche in quattro tipi, in base alla forma delle regole, e mostra che a ogni tipo corrisponde un modello di macchina e una classe di linguaggi. Le classi sono annidate: ogni livello contiene strettamente quello sotto.
Le grammatiche in generale
Una grammatica generale ha variabili, terminali, una variabile iniziale e regole della forma α → β, dove α e β sono stringhe di variabili e terminali e α contiene almeno una variabile. La gerarchia nasce imponendo restrizioni sempre più forti sulla forma di queste regole.
I quattro livelli
| Tipo | Grammatiche | Forma delle regole | Modello di macchina |
|---|---|---|---|
| 0 | Senza restrizioni | α → β | Macchina di Turing |
| 1 | Dipendenti dal contesto | αAβ → αγβ, con γ non vuota | Automa limitato linearmente |
| 2 | Libere dal contesto | A → γ | Automa a pila non deterministico |
| 3 | Regolari | A → aB oppure A → a | Automa a stati finiti |
Tipo 3: linguaggi regolari
Le regole hanno a destra un terminale eventualmente seguito da una sola variabile. Una derivazione assomiglia a un cammino in un automa: la variabile corrente è lo stato, il terminale prodotto è il simbolo letto. Infatti le grammatiche regolari generano esattamente i linguaggi riconosciuti dagli automi finiti.
Esempio: stringhe su {a, b} che terminano con b. S → aS | bS | b.
Tipo 2: linguaggi liberi dal contesto
A sinistra c'è una sola variabile, a destra qualsiasi cosa. Si possono descrivere strutture annidate. L'automa corrispondente è l'automa a pila.
Esempio che separa il tipo 2 dal tipo 3: {aⁿbⁿ : n ≥ 0}, generato da S → aSb | ε, che non è regolare.
Tipo 1: linguaggi dipendenti dal contesto
Una variabile A si può riscrivere come γ solo quando compare nel contesto α…β. Una caratterizzazione equivalente richiede che le regole non accorcino mai la stringa (|α| ≤ |β|). La macchina corrispondente è l'automa limitato linearmente: una macchina di Turing non deterministica che può usare solo lo spazio occupato dall'input.
Esempio che separa il tipo 1 dal tipo 2: {aⁿbⁿcⁿ : n ≥ 1}. Si dimostra con il pumping lemma per linguaggi liberi dal contesto che non è di tipo 2, mentre esiste una grammatica non accorciante che lo genera.
Tipo 0: linguaggi ricorsivamente enumerabili
Nessuna restrizione: le regole possono anche accorciare la stringa. Le grammatiche di tipo 0 generano esattamente i linguaggi ricorsivamente enumerabili, cioè quelli per cui esiste una macchina di Turing che accetta tutte e sole le stringhe del linguaggio (potendo non terminare sulle altre).
Esempio che separa il tipo 0 dal tipo 1: ogni linguaggio di tipo 1 è decidibile, mentre il linguaggio del problema dell'arresto è ricorsivamente enumerabile ma non decidibile. Quindi sta al tipo 0 e non al tipo 1.
Un livello nascosto: i linguaggi decidibili
La tabella classica ha quattro righe, ma fra il tipo 1 e il tipo 0 c'è una classe importante che non corrisponde a un tipo di grammatica: i linguaggi decidibili (o ricorsivi), per cui esiste una macchina di Turing che termina sempre rispondendo sì o no. Vale:
regolari ⊂ liberi dal contesto ⊂ dipendenti dal contesto ⊂ decidibili ⊂ ricorsivamente enumerabili
e tutte le inclusioni sono strette.
Che cosa si può decidere a ogni livello
Più si sale, più il modello è espressivo e meno domande hanno risposta algoritmica.
| Problema | Tipo 3 | Tipo 2 | Tipo 1 | Tipo 0 |
|---|---|---|---|---|
| Appartenenza di una stringa | Sì, tempo lineare | Sì, tempo polinomiale | Sì | No |
| Linguaggio vuoto | Sì | Sì | No | No |
| Equivalenza di due descrizioni | Sì | No | No | No |
Alcune righe meritano attenzione. Per il tipo 1 l'appartenenza è decidibile, ma il problema è in generale PSPACE-completo, quindi può essere molto costoso. Per il tipo 2 il vuoto è decidibile (basta verificare se la variabile iniziale può generare qualche stringa di terminali), mentre l'equivalenza di due grammatiche libere dal contesto è indecidibile.
A che cosa serve, concretamente
La gerarchia è uno strumento di progettazione. Quando si definisce un formato o un linguaggio, scegliere il livello più basso che basta significa ottenere strumenti più semplici e più garanzie:
- per token, identificatori e numeri basta il tipo 3, e si usano automi finiti;
- per la sintassi annidata di un linguaggio di programmazione serve il tipo 2, e si usano parser deterministici;
- i vincoli che dipendono dal contesto, come «ogni variabile deve essere dichiarata prima dell'uso», di solito non si mettono nella grammatica ma si controllano in una fase successiva, con codice ordinario.
È una divisione del lavoro che nasce direttamente dalla teoria: ogni livello si usa dove funziona bene.
In sintesi
- La gerarchia di Chomsky classifica le grammatiche in quattro tipi in base alla forma delle regole.
- A ogni tipo corrisponde una macchina: automa finito, automa a pila, automa limitato linearmente, macchina di Turing.
- Le classi sono annidate in modo stretto, con esempi separatori come aⁿbⁿ e aⁿbⁿcⁿ.
- Fra tipo 1 e tipo 0 si trova la classe dei linguaggi decidibili.
- Salendo di livello cresce l'espressività e diminuiscono le domande decidibili.
