La gerarchia di Chomsky è un insieme di classi di grammatiche formali che generano linguaggi formali. La gerarchia di queste grammatiche, chiamate anche grammatiche a struttura sintagmatica (phrase structure grammars), fu descritta da Noam Chomsky nel 1956 (vedi ^*).

Grammatiche formali

---

Una grammatica formale consiste di un insieme finito di simboli terminali (le lettere di una parola nel linguaggio formale), un insieme finito di simboli non terminali, un insieme finito di regole di produzione (con una lato sinistro ed un lato destro), ed infine un simbolo iniziale. Una regola di produzione può essere applicata ad una parola rimpiazzando il lato sinistro con il lato destro. Una derivazione è una sequenza di regole di produzione. In questo modo una grammatica definisce un linguaggio formale con tutte le parole costituite dai soli simboli terminali che possono essere raggiunti dal simbolo iniziale attraverso derivazioni.

I simboli non terminali sono genericamente rappresentati da lettere in maiuscolo, i terminali da lettere in minuscolo, e il simbolo iniziale da $S$. Per esempio, la grammatica con simboli terminali $\backslash \{a,\; b\backslash \}$, e simboli non terminali $\backslash \{S,\; A,\; B\backslash \}$, e regole di produzione

$S$ → $ABS$

$S$ → ε (dove ε è la stringa vuota)

$BA$ → $AB$

$BS$ → $b$

$Bb$ → $bb$

$Ab$ → $ab$

$Aa$ → $aa$

e il simbolo iniziale $S$, definisce il linguaggio composto da tutte le parole nella forma $a^n\; b^n$ (Ad esempio $n$ ripetizioni di $a$ seguite da $n$ ripetizioni di $b$).

Quella seguente è una semplice grammatica che definisce un linguaggio simile: Simboli terminali $\backslash \{p,\; q\backslash \}$, simboli non terminali $\backslash \{S\backslash \}$, simbolo iniziale $S$, regole di produzione

$S$ → $pSq$

$S$ → ε

Vedi l'articolo sulla grammatica formale per una spiegazione più elaborata.

La gerarchia

---

La gerarchia di Chomsky è composta dai seguenti livelli:

• Grammatiche di tipo-0 (grammatiche illimitate) include tutte le grammatiche formali. Queste grammatiche generano esattamente tutti i linguaggi che possono essere riconosciuti da una Macchina di Turing. Questi linguaggi sono anche conosciuti come linguaggi ricorsivamente enumerabili. Da notare che questi linguaggi sono differenti dai linguaggi ricorsivi che possono essere riconosciuti da una macchina di Turing che termina sempre.

• Grammatiche di tipo-1 (grammatiche sensibili al contesto) generano linguaggi sensibili al contesto. Queste grammatiche hanno regole della forma $\backslash alpha\; A\backslash beta\; \backslash rightarrow\; \backslash alpha\backslash gamma\backslash beta$ con $A$ simbolo non terminale e $\backslash alpha$, $\backslash beta$ e $\backslash gamma$ stringhe di simboli terminali e non terminali. Le stringhe $\backslash alpha$ e $\backslash beta$ possono essere vuote, ma la $\backslash gamma$ non deve essere vuota. La regola di produzione $S\; \backslash rightarrow\; \backslash epsilon$ è permessa se $S$ non appare nel lato destro delle regole di produzione. I linguaggi descritti da queste grammatiche sono esattamente tutti i linguaggi che possono essere riconosciuti da una macchina di Turing non deterministica nella quale il nastro è limitato da un numero costante di volte la lunghezza dell'input.

• Grammatiche di tipo-2 (grammatiche context-free) generano linguaggi context-free. Queste grammatiche sono definite da regole nella forma $A\; \backslash rightarrow\; \backslash gamma$ con $A$ simbolo non terminale e $\backslash gamma$ una stringa di simboli terminali e non terminali. Questi linguaggi sono esattamente tutti i linguaggi che possono essere riconosciuti da un automa a pila non deterministico. I linguaggi context free sono teoricamente le basi per la sintassi di molti linguaggi di programmazione (Analisi sintattica).

• Grammatiche di tipo-3 (grammatiche lineari (o regolari)) generano linguaggi lineari (o linguaggi regolari). Questo tipo di grammatiche restringe le sue regole ad un singolo simbolo non terminale nel lato sinistro della produzione e nel lato destro un singolo simbolo terminale, possibilmente seguito (o preceduto, ma non entrambe le forme nella stessa grammatica) da un singolo simbolo non terminale. La regola $S\; \backslash rightarrow\; \backslash epsilon$ è permessa anche qui se $S$ non compare nel lati destri delle regole di produzione. Questi linguaggi sono esattamente tutti i linguaggi riconosciuti da un automa a stati finiti. Oltretutto, questa famiglia di linguaggi formali può essere ottenuta con espressioni regolari. I linguaggi lineari sono communemente usati per definire modelli di ricerca (search patterns) e la struttura lessicale dei linguaggi di programmazione (Analisi lessicale (informatica)).

Nota che l'insieme delle grammatiche corrispondente ai linguaggi ricorsivi non è un membro di questa gerarchia.

Ogni linguaggio lineare è context-free (libero da contesto), ogni linguaggio context-free è sensibile al contesto e ogni linguaggio sensibile al contesto è ricorsivo, ed in fine ogni linguaggio ricorsivo è enumerabile ricorsivamente. Queste sono inclusioni proprie, nel senso che esistono linguaggi enumerabili ricorsivamente che sono non ricorsivi, linguaggi ricorsivi che sono non sensibili al contesto, linguaggi sensibili al contesto che sono non context-free e linguaggi context-free che sono non regolari.

La seguente tabella riassume i quattro tipi di grammatiche secondo Chomsky, la classe dei linguaggi generati, il tipo di automa che li riconosce e la forma che devono avere le sue regole.

Grammatica	Linguaggio	Automa	Regole di produzione
Tipo-0	Ricorsivamente enumerabile	Macchina di Turing	Nessuna restrizione
Tipo-1	Sensibile al contesto	Macchina di Turing non deterministica e limitata linearmente	$\backslash alpha\; A\backslash beta\; \backslash rightarrow\; \backslash alpha\backslash gamma\backslash beta$
Tipo-2	Context-free	Automa a pila non deterministico	$A\; \backslash rightarrow\; \backslash gamma$
Tipo-3	Lineare (o Regolare)	Automa a stati finiti	$A\; \backslash rightarrow\; a$ e o $A\; \backslash rightarrow\; aB$ o $A\; \backslash rightarrow\; Ba$

Riferimenti

---

1. Noam Chomsky: Three models for the description of language, IRE Transactions on Information Theory, 2 (1956), pagine 113-124
2. Noam Chomsky: On certain formal properties of grammars, Information and Control, 1 (1959), pagine 91-112

Collegamenti esterni

---

• http://www.staff.ncl.ac.uk/hermann.moisl/ell236/lecture5.htm

Linguaggi formali

Chomsky-hiërargie | Йерархия на Чомски | Chomského hierarchie | Chomsky-Hierarchie | Chomsky–Schützenberger hierarchy | Jerarquía de Chomsky | Chomskyn hierarkia | Hiérarchie de Chomsky | チョムスキー階層 | 촘스키 위계 | Hierarchia Chomsky'ego | Hierarquia de Chomsky | Ierarhia Chomsky | Chomského hierarchia | 乔姆斯基谱系