Il legame tra linguistica e informatica è molto più profondo di quanto si possa pensare: è proprio dallo studio della struttura dei linguaggi che nascono alcune delle idee fondamentali dell’informatica moderna. La formalizzazione del linguaggio ha avuto inizio negli anni ‘50 del secolo scorso, con lo scopo di determinare le regolarità sintattiche dei linguaggi naturali. Questa branca ha rivoluzionato non solo la linguistica, ma anche la matematica e soprattutto l’informatica, rappresentando la spina dorsale nella strutturazione dei linguaggi di programmazione e nella comunicazione tra macchine.

Dato un alfabeto, un linguaggio è un insieme di frasi (dette stringhe) che seguono precise regole sintattiche. Tali regole possono essere formulate in vari modi: quello più intuitivo è quello delle grammatiche, tramite cui siamo in grado di generare frasi di senso compiuto. Nel linguaggio naturale (ovvero quello che usiamo ogni giorno) questo accade per sostituzioni successive ed annidate. Per esempio, una frase semplice potrebbe essere strutturata come

frase = soggetto + verbo + oggetto

e a loro volta, soggetto e oggetto potrebbero essere costituiti da

soggetto = articolo + nome
oggetto = articolo + nome.

Potremmo rappresentare formalmente queste sostituzioni come

S → NvO
Nv → anv
vO → van

• S: è il simbolo iniziale (start). In questo caso è la frase;
• simboli non terminali: simboli che vanno sostituiti per raggiungere la forma finale della frase (di solito indicati con lettere maiuscole). In questo caso sono N (soggetto) e O (oggetto);
• simboli terminali: simboli che compaiono nella frase finale (di solito indicati con lettere minuscole). In questo caso sono a (articolo), n (nome) e v (verbo).

Questo tipo di rappresentazione viene usata nell’ambito delle grammatiche formali per formulare le regole che deve seguire un linguaggio e, potenzialmente, generare tutte le possibili frasi che vi appartengono: si inizia da S e si operano sostituzioni successive secondo le regole fino a che non si ottiene una frase fatta di soli simboli terminali.

Grazie a questa logica delle sostituzioni, si possono creare anche linguaggi “astratti” (non naturali) a partire da una grammatica. Consideriamo ad esempio un alfabeto costituito da due sole lettere a e b, e le regole grammaticali

(1) S → aSb
(2) S → ba

Il linguaggio generato contiene stringe come:

• ba (regola 2)
• abab (regole 1 → 2)
• aababb (1 → 1 → 2)
• aaababbb (1 → 1 → 1 → 2) etc.

Può essere più complesso, invece, stabilire se una stringa appartenga o meno a un linguaggio. Per farlo, ad esempio, potremmo applicare le regole in senso inverso, cercando di risalire al simbolo iniziale $S$: se ci riusciamo, la stringa appartiene al linguaggio, se invece non è possibile, la stringa non vi appartiene. Questo problema è particolarmente interessante dal punto di vista algoritmico: richiede infatti di comprendere quali procedure siano necessarie per riconoscere una stringa, e quali limiti queste procedure possano avere. In questo senso, studiare i linguaggi equivale anche a studiare gli algoritmi che li elaborano, se li interpretiamo come processi che trasformano e analizzano simboli secondo regole precise. È proprio in questo contesto che si inserisce il lavoro di Noam Chomsky, che ha introdotto una classificazione delle grammatiche (e, quindi, dei linguaggi) in quattro classi annidate, nota come gerarchia di Chomsky.

La gerarchia di Chomsky

La gerarchia di Chomsky classifica i linguaggi formali in base alla grammatica che li genera, individuando quattro classi con grado di generalità decrescente: grammatiche di tipo 0, 1, 2, 3.

Grammatiche di tipo 0

È la classe più generale. Le grammatiche che la soddisfano sono caratterizzate da regole del tipo

α → β

dove α e β sono costituiti da simboli terminali e/o non-terminali e possono essere di lunghezza arbitraria (anche vuoti). Questo significa che, nel costruire una stringa, è possibile sia aggiungere che rimuovere simboli. Supponiamo di voler verificare che una stringa appartenga o meno ad una grammatica di tipo 0 applicando le regole grammaticali in senso inverso e cercando di risalire al simbolo iniziale S. Poiché in queste grammatiche è possibile sia togliere che aggiungere simboli, le sequenze di regole da applicare sono potenzialmente infinite. Di conseguenza, se una stringa non appartiene al linguaggio, non riusciremo a verificarlo in un tempo finito: per farlo, dovremmo escludere tutte le possibili sequenze di trasformazioni che terminano in S, ma queste sono infinite. I linguaggi che appartengono a questa classe sono detti ricorsivamente enumerabili.

Grammatiche di tipo 1

Questo tipo di grammatiche ha una definizione simile alla precedente, con un requisito aggiuntivo: le regole di sostituzione prevedono che le stringhe non si accorcino mai. In formule si scrive

α → β con ∣β∣≥∣α∣.

Queste grammatiche sono dette context-sensitive, poiché α può essere una combinazione arbitrariamente lunga di simboli, che dovranno apparire in quella forma esatta perché vengano sostituiti con β. In questo caso, quindi, non è necessario un tempo infinito per verificare che una stringa non appartenga al linguaggio: ogni trasformazione, applicata in senso inverso, accorcia la stringa (o la mantiene di lunghezza invariata). Non c’è però una sequenza univoca di trasformazioni da applicare che conduca ad una conclusione definitiva (cioè che la stringa appartenga o non appartenga al linguaggio). Per vederlo, consideriamo ad esempio un alfabeto di una sola lettera a e la grammatica

(1) S → aAa
(2) aA → aaA oppure aa.

Proviamo a verificare che la stringa $aaa$ appartiene al linguaggio. Come primo tentativo, potremmo applicare la regola (2) alle ultime due lettere della stringa, ottenendo aaa → aaA → aA. Vediamo però che questa opzione non permette di risalire ad S (e, quindi, verificare che la stringa appartiene al linguaggio), perché non ci sono trasformazioni nella grammatica che possiamo applicare ad aA. È necessario quindi tornare sui nostri passi ed applicare le regole in modo diverso: ad esempio, possiamo applicare la regola (2) alle prime due lettere, e poi la regola (1) aaa → aAa → S verificando così la nostra ipotesi. In questo esempio la struttura della grammatica e della stringa è particolarmente semplice, ma la complessità cresce velocemente con la lunghezza della stringa e il numero di regole grammaticali, poiché aumentano le combinazioni di trasformazioni da verificare.

Le grammatiche viste fino ad ora hanno soprattutto importanza in informatica teorica, in particolare in relazione con le Macchine di Turing e il problema della decidibilità, che verranno trattate in un articolo successivo. Le grammatiche di tipo 2 e 3 sono invece più vicine alla nostra esperienza quotidiana.

Grammatiche di tipo 2

Le grammatiche di tipo 2 rappresentano una classe fondamentale nella teoria dei linguaggi formali, poiché vi appartengono le operazioni aritmetiche, i linguaggi di programmazione e, in una certa misura, il linguaggio naturale (ovvero, quello che usiamo quotidianamente per comunicare). Le sue regole grammaticali sono caratterizzate dalla presenza di singoli simboli non terminali che possono essere sostituiti da stringhe terminali e non terminali. In formule

A → $\gamma$.

Questa grammatica viene definita context-free: non è necessario sapere quali simboli appaiano assieme ad A per applicare la regola A → $\gamma$. Grazie a questa struttura, possiamo associare al simbolo di sostituzione → il significato di costituito da e utilizzare una rappresentazione ad albero nell’analisi delle stringhe: procedendo dalla radice S l’analisi si dirama verso il basso aumentando progressivamente la granularità, finché ogni ramo non termina in una foglia: questo processo trasforma una sequenza di caratteri in una struttura annidata, dove ogni sottogruppo di simboli ha un’identità autonoma e definita.

Consideriamo ad esempio la stringa “3 + 5 = 8”. Questa può essere ricondotta a una struttura del tipo

Operazione $\overset{costituita\,da}{\rightarrow}$ Risultato & Espressione
Espressione $\overset{costituita\,da}{\rightarrow}$ Addendo & Somma & Addendo

Lo stesso avviene nel linguaggio naturale: la frase “Il gatto beve il latte” può essere generata come

Frase $\overset{costituita\,da}{\rightarrow}$ Sintagma Nominale & SintagmaVerbale
Sintagma Nominale $\overset{costituita\,da}{\rightarrow}$ Articolo & Nome
Sintagma verbale $\overset{costituita\,da}{\rightarrow}$ Verbo & Oggetto
Oggetto $\overset{costituita\,da}{\rightarrow}$ Articolo & Nome

Dalla nostra esperienza quotidiana sappiamo però che nel linguaggio esistono dipendenze dal contesto, come ad esempio la concordanza tra soggetto e verbo. Questo suggerisce che le grammatiche context-free, pur essendo molto efficaci nel descrivere la struttura sintattica tramite rappresentazioni ad albero, non siano sempre sufficienti. Di conseguenza, il linguaggio naturale richiede formalismi più espressivi, che tengano conto del contesto, pur senza coincidere completamente con le grammatiche context-sensitive della gerarchia di Chomsky.

Grammatiche di tipo 3

Le grammatiche di tipo 3 sono costituite da simboli non terminali che possono essere sostituiti da simboli terminali, o al più un simbolo terminale e uno non terminale (a destra oppure a sinistra), ovvero

A → a, A → aB
oppure
A → a, A → Ba

Questo rende la generazione delle stringhe (o la loro analisi) molto più semplice dei casi precedenti, visto che la sostituzione avverrà sempre da destra verso sinistra o da sinistra verso destra.

Le grammatiche di tipo 3 sono particolarmente utili nella vita quotidiana e alla base delle espressioni regolari, ovvero sequenze di caratteri che identificano insiemi di stringhe. Le espressioni regolari vengono utilizzate ad esempio nella verifica della struttura di un indirizzo mail come NOME_UTENTE@DOMINIO.TLD oppure di una data GG/MM/AAAA. Consideriamo questo secondo caso a titolo di esempio. Possiamo costruire la grammatica del linguaggio come

S → dG
G → d / M
M → d d / A
A → dddd

dove:

• G è un simbolo non terminale per il giorno
• M è un simbolo non terminale per il mese
• A è un simbolo non terminale per l’anno
• d è una cifra qualsiasi da 0 a 9 (tramite regole più strutturate è possibile vincolare la produzione di anni “validi”, ovvero che non inizino per 0 ad esempio).

Come possiamo vedere, l’albero che rappresenta la stringa è molto sbilanciato: questo avviene perché i simboli non terminali appaiono sempre a destra (o sempre a sinistra) in questo tipo di grammatiche.

Conclusione

La formalizzazione del linguaggio ha costituito un passaggio fondamentale nello sviluppo dell’informatica teorica. Come abbiamo visto in questo articolo, classificare le grammatiche non è solo un mero esercizio, ma un modo per comprendere la struttura dei problemi e degli algoritmi. La gerarchia di Chomsky evidenzia infatti il legame tra espressività dei linguaggi e capacità computazionali, mostrando come a grammatiche più complesse corrispondano modelli di calcolo più versatili. Questa progressione (dalle grammatiche di tipo 3, le più rigide, a quelle di tipo 0, le più flessibili) riflette i limiti e le capacità dei sistemi di calcolo. In questo senso, la gerarchia non è soltanto una classificazione, ma uno strumento per orientarsi nella teoria della computazione. Questo legame diventa ancora più significativo considerando la relazione con le macchine di Turing, che rappresentano il modello più generale di calcolo.