Gerarchia di Chomsky

Da Wikipedia, l'enciclopedia libera.
Se riscontri problemi nella visualizzazione dei caratteri, clicca qui.

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[1][2].

Grammatiche formali[modifica | modifica sorgente]

Exquisite-kfind.png Per approfondire, vedi grammatica formale.

Una grammatica formale G è una quadrupla G=(N,T,S,P), ove N è un insieme finito e non vuoto di simboli detto alfabeto non terminale, T è un insieme finito e non vuoto di simboli detto alfabeto terminale (le lettere di una parola nel linguaggio formale), P è una relazione binaria di cardinalità in altre parole un insieme di regole di produzione (con un lato sinistro ed un lato destro), ed infine S appartenente a N è detto Assioma, e rappresenta il simbolo non terminale di inizio 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 \{a, b\}, e simboli non terminali \{S, A, B\}, e regole di produzione

S\to ABS
S\to \varepsilon (dove \varepsilon è la stringa vuota)
BA\to AB
BS\to b
Bb\to bb
Ab\to ab
Aa\to aa

e il simbolo iniziale S, definisce il linguaggio composto da tutte le parole nella forma  a^n b^n (Ovvero tutte le stringhe formate da n ripetizioni di a seguite da n ripetizioni di b, come ad esempio aaabbb per n=3 o aaaaabbbbb per n=5).

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

S\to pSq
S\to \varepsilon

La gerarchia[modifica | modifica sorgente]

Gerarchia-di-Chomsky.jpg

La gerarchia di Chomsky è composta dai seguenti livelli:

  • Grammatiche di tipo-0 (grammatiche illimitate) include tutte le grammatiche formali. Queste grammatiche hanno regole della forma \alpha A\beta \rightarrow \alpha\gamma\beta con A simbolo non terminale, \alpha, \beta e \gamma stringhe di simboli terminali e non terminali. Queste grammatiche ammettono anche derivazioni che diminuiscono la lunghezza della frase, ad esempio le ε-produzioni, quindi \gamma può essere vuota. Queste grammatiche generano esattamente tutti i linguaggi che possono essere accettati 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. I linguaggi di tipo-0 sono semidecidibili secondo Turing (dato un linguaggio L di tipo-0 è sempre possibile definire una MT ℳ tale che se una stringa s \in L allora ℳ termina la computazione accettando s, se invece s \not \inL ℳ può non terminare la computazione di s).
  • Grammatiche di tipo-1 (grammatiche dipendenti dal contesto) generano linguaggi dipendenti dal contesto. Queste grammatiche hanno regole della forma \alpha A\beta \rightarrow \alpha\gamma\beta con A simbolo non terminale e \alpha, \beta e \gamma stringhe di simboli terminali e non terminali (qualunque regola di produzione che riduca la lunghezza delle stringhe non è ammessa). Le stringhe \alpha e \beta possono essere vuote, ma la \gamma non deve essere vuota. 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-3 (grammatiche regolari) generano 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, che può essere seguito (o preceduto, ma non entrambe le forme nella stessa grammatica) da un singolo simbolo non terminale. La regola S \to \varepsilon è 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 regolari sono comunemente usati per definire modelli di ricerca (search patterns) e la struttura lessicale dei linguaggi di programmazione (Analisi lessicale).

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

La grammatica di tipo-0 è l'unica che può generare la stringa vuota. È possibile estendere le grammatiche di tipo-1, 2 e 3 in modo tale che possono generare lo stesso linguaggio arricchito della stringa vuota. La regola di produzione S \rightarrow \varepsilon è permessa se S non appare nel lato destro delle regole di produzione. L'introduzione delle ε-produzioni ha conseguenze diverse a seconda del tipo di grammatica. Nel caso delle grammatiche di tipo-2 o 3 le ε-produzioni non aumentano il potere espressivo della grammatica. Viceversa le grammatiche di tipo-1 si trasformano in grammatiche di tipo-0, i.e. aumenta il potere espressivo della grammatica.

Ogni linguaggio regolare è libero dal contesto, ogni linguaggio libero dal contesto è dipendente dal contesto (è infatti un caso particolare dove le stringhe \alpha e \beta sono obbligatoriamente vuote) e ogni linguaggio dipendente dal contesto è ricorsivo, ed infine 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 dipendenti dal contesto, linguaggi dipendenti dal contesto che sono non liberi dal contesto e linguaggi liberi dal contesto che sono non regolari.

Note[modifica | modifica sorgente]

  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[modifica | modifica sorgente]

Teoria degli automi: linguaggi formali e grammatiche formali
Gerarchia di Chomsky Grammatica formale Linguaggio Automa minimo
Tipo-0 (illimitato) Ricorsivamente enumerabile Macchina di Turing
(illimitato) Ricorsivo Decider
Tipo-1 Dipendente dal contesto Dipendente dal contesto Automa lineare
Tipo-2 Libera dal contesto Libero dal contesto Automa a pila ND
Tipo-3 Regolare Regolare A stati finiti
Ciascuna categoria di linguaggio o grammatica è un sottoinsieme proprio della categoria immediatamente sottostante.