Gerarchia di Chomsky

In scienza teorica informatica , teoria dei linguaggi e calcolabilità , la gerarchia di Chomsky (a volte chiamato il Chomsky- Schützenberger gerarchia ) è una classificazione di grammatiche formali (e, per estensione, dei rispettivi linguaggi formali generati da grammatiche), descritto da Noam Chomsky in 1956 .

Presentazione

La gerarchia introdotta da Noam Chomsky si basa sul modello grammaticale formale . Definisce le classi della sua gerarchia come possibili modelli per la descrizione delle proprietà strutturali dei linguaggi naturali. Noam Chomsky ha proposto una classificazione in quattro tipi di lingue, dal tipo 0 al tipo 3. Questa terminologia iniziale è stata mantenuta, ma ora altri nomi sono più comuni. Chomsky ha presentato queste famiglie in termini di grammatiche formali e le varie classi di grammatiche sono definite da restrizioni successive sotto forma di regole.

Una proprietà notevole della classificazione di Chomsky è che, per ogni tipo, esiste una famiglia di automi che accetta esattamente linguaggi di quel tipo. Questi controller variano nella natura e nell'uso della memoria ausiliaria. La traduzione in classi di complessità è meno chiara: i linguaggi razionali (tipo 3) sono in DTIME (n), i linguaggi algebrici (tipo 2) in DTIME (n 3 ), i linguaggi contestuali (tipo 1) in DTIME ( n M ), dove M dipende dalla grammatica, ma non è vero il contrario.

La classificazione di Chomsky, ripresa in quasi tutti i manuali di insegnamento dell'informatica, si è rivelata molto fruttuosa nelle sue applicazioni, in particolare nella progettazione e analisi dei linguaggi di programmazione e nella compilazione di questi linguaggi. I linguaggi razionali e algebrici sono stati oggetto in passato di ampi studi teorici. Le lingue sensibili al contesto vengono utilizzate principalmente nella descrizione delle lingue naturali.

Quattro classi di grammatiche e lingue

Chomsky ha definito quattro classi di grammatiche, denominate da tipo 0 a tipo 3, e quindi anche quattro classi di lingue, generate da queste grammatiche gerarchicamente annidate:

1. I linguaggi di tipo 0 sono i più generali: sono linguaggi enumerabili ricorsivamente .
2. Le lingue di tipo 1 sono lingue contestuali , in inglese "sensibili al contesto".
3. Le lingue di tipo 2 sono chiamate lingue algebriche o "libere dal contesto", in inglese "libere dal contesto".
4. I linguaggi di tipo 3 sono linguaggi "normali" o linguaggi razionali .

Tutte le lingue di tipo 3 sono lingue di tipo 2. Tutte le lingue di tipo 2 sono lingue di tipo 1. Tutte le lingue di tipo 1 sono lingue di tipo 0. La tabella seguente riassume la corrispondenza tra tipi di grammatica, lingue e macchine.

Grammatica	Regole di produzione	Linguaggio	Macchina
digitare 0	α→β{\ displaystyle \ alpha \ rightarrow \ beta}	ricorsivamente enumerabile	Macchina di Turing
tipo 1	αAβ→αγβ{\ Displaystyle \ alpha A \ beta \ rightarrow \ alpha \ gamma \ beta}	contestuale	Automa delimitato linearmente
tipo 2	A→γ{\ displaystyle A \ rightarrow \ gamma}	algebrico	Automa a pila non deterministico
tipo 3	A→aB,A→a{\ Displaystyle A \ rightarrow aB, \ quad A \ rightarrow a}	razionale	Automa finito

Nella presentazione formale di seguito, il vocabolario della grammatica, composto da simboli terminali e non terminali, è l'insieme di simboli non terminali ed è la parola vuota. V{\ displaystyle V}NON{\ displaystyle N}ε{\ displaystyle \ varepsilon}

Tipo 0: grammatiche generali

Non ci sono restrizioni sulle regole. Hanno la forma:

α→β(α∈V∗NONV∗,β∈V∗){\ displaystyle \ alpha \ rightarrow \ beta \ quad \ quad (\ alpha \ in V ^ {*} NV ^ {*}, \ beta \ in V ^ {*})}

Queste grammatiche generano la classe dei linguaggi enumerabili ricorsivamente . Queste sono esattamente le lingue riconoscibili da una macchina di Turing . Il problema se una parola appartiene a una lingua di questa classe è indecidibile .

Tipo 1: grammatiche contestuali

Le regole sono nella forma:

αAβ→αγβ(A∈NON,α,β,γ∈V∗,γ≠ε){\ displaystyle \ alpha A \ beta \ rightarrow \ alpha \ gamma \ beta \ qquad (A \ in N, \ alpha, \ beta, \ gamma \ in V ^ {*}, \ gamma \ neq \ varepsilon)}

In altre parole, qualsiasi regola include un non terminale circondato da due parole che descrivono il contesto in cui la variabile può essere sostituita. Queste grammatiche sono chiamate contestuali (in inglese sensibili al contesto ), perché la sostituzione di un elemento non terminale può dipendere dagli elementi che lo circondano: il suo contesto. I linguaggi prodotti, chiamati linguaggi contestuali o sensibili al contesto , sono esattamente quelli riconosciuti da una macchina di Turing non deterministica con memoria limitata linearmente, comunemente chiamati automi limitati linearmente . Esistono altre formulazioni equivalenti per le grammatiche che definiscono i linguaggi contestuali.

Tipo 2: grammatiche non contestuali o algebriche

Le regole sono nella forma:

A→γ(A∈NON,γ∈V∗){\ Displaystyle A \ rightarrow \ gamma \ qquad (A \ in N, \ gamma \ in V ^ {*})}

Tale regola può essere vista come una regola contestuale in cui il contesto delle regole è vuoto, a condizione che il membro giusto non sia la parola vuota. L'aggettivo "non contestuale" esprime il fatto che i simboli non terminali vengono trattati indipendentemente da dove compaiono. Queste grammatiche generano linguaggi esattamente algebrici , chiamati anche linguaggi privi di contesto, linguaggi contestuali o linguaggi non contestuali. Sono riconosciuti da un automa alimentato a batteria . γ{\ displaystyle \ gamma}

Tipo 3: grammatiche regolari

Le grammatiche regolari sono grammatiche lineari sinistra o grammatiche lineari destra:

• Nelle grammatiche lineari a sinistra , le regole sono nella forma:

A→Ba,A→a(A,B∈NON,a∈T){\ Displaystyle A \ rightarrow Ba, \ quad A \ rightarrow a \ qquad (A, B \ in N, a \ in T)}

• Nelle grammatiche lineari a destra , le regole sono nella forma:

A→aB,A→a(A,B∈NON,a∈T){\ Displaystyle A \ rightarrow aB, \ quad A \ rightarrow a \ qquad (A, B \ in N, a \ in T)}

Le grammatiche regolari generano linguaggi razionali . In effetti, una grammatica regolare si trasforma facilmente in un automa finito ( teorema di Kleene ).

Attenzione, non possiamo autorizzare contemporaneamente i due tipi di regole in una grammatica senza uscire dalla classe dei linguaggi razionali: si ottengono le grammatiche lineari che costituiscono una classe intermedia tra il tipo 2 e il tipo 3. Le regole di una grammatica lineare sono della forma:

A→aBb,A→a(A,B∈NON,a,b∈T∪ε){\ Displaystyle A \ rightarrow aBb, \ quad A \ rightarrow a \ qquad (A, B \ in N, a, b \ in T \ cup \ varepsilon)}

Inclusione delle famiglie

• La classe dei linguaggi razionali (tipo 3) è strettamente inclusa nella classe dei linguaggi algebrici (tipo 2).

• La classe dei linguaggi contestuali (tipo 1) è strettamente inclusa nella classe dei linguaggi enumerabili ricorsivamente (tipo 0).

• L'inclusione della classe dei linguaggi algebrici (tipo 2) nella classe dei linguaggi contestuali (tipo 1) deve essere chiarita perché un linguaggio contestuale non contiene mai la parola vuota ε. La dichiarazione esatta è:

Una lingua algebrica che non contiene la parola vuota è una lingua contestuale o, equivalentemente: Una lingua algebrica è una lingua contestuale eventualmente aumentata dalla parola vuota .

Esempi di lingue

• Lingue regolari: .
  a∗b∗,(aaab)∗,{a3io:io>0}{\ displaystyle a ^ {*} b ^ {*}, \ quad (aaab) ^ {*}, \ quad \ {a ^ {3i}: i> 0 \}}
• Linguaggi algebrici non razionali :, l'insieme dei palindromi (che è anche un linguaggio lineare, come il precedente), il linguaggio di Dyck
  {aiobio:io>0}{\ displaystyle \ {a ^ {i} b ^ {i}: i> 0 \} \,}
• Lingue sensibili al contesto che non sono algebrica: .
  {aiobiovsio:io>0},{aiobKvsiodK:io>0,K>0},{uu:u∈{a,b}∗}{\ displaystyle \ {a ^ {i} b ^ {i} c ^ {i}: i> 0 \}, \ quad \ {a ^ {i} b ^ {k} c ^ {i} d ^ {k }: i> 0, k> 0 \}, \ quad \ {uu: u \ in \ {a, b \} ^ {*} \}}

Vedi anche gli esempi nella pagina della grammatica formale . La teoria dei linguaggi formali ha molti strumenti per affermare o invalidare il tipo di un linguaggio (razionale, algebrico, ecc.). La costruzione esplicita di una grammatica che riconosce una data lingua non è sempre facile.

Affinamento della gerarchia di Chomsky

La gerarchia originale di Chomsky consisteva di quattro classi. Altre classi sono spesso intervallate:

• tra tipo 0 e tipo 1, linguaggi ricorsivi , accettati dalle macchine di Turing che si fermano sempre;
• tra tipo 1 e tipo 2, lingue con grammatiche indicizzate , definite da grammatiche più generali che grammatiche contestuali;
• tra il tipo 2 e il tipo 3, linguaggi algebrici deterministici , per i quali esiste una caratterizzazione per automa, ma non per grammatica;
• anche tra il tipo 2 e il tipo 3, linguaggi lineari, generati da grammatiche lineari .

L' albero delle grammatiche adiacenti definisce una famiglia tra linguaggi algebrici e linguaggi sensibili al contesto. Sono accettati dagli automi a batteria di bordo . Queste grammatiche fanno parte delle grammatiche che consentono una migliore comprensione della struttura delle lingue naturali, raggruppate sotto il nome linguaggio leggermente sensibile al contesto  (en) .

Esistono altri affinamenti, che dimostrano che la struttura non è “lineare”: ad esempio, se confrontiamo linguaggi lineari e linguaggi algebrici deterministici, vediamo che queste famiglie non sono contenute né l'una nell'altra.

Estensione di questa gerarchia

La gerarchia di Chomsky riguarda solo il dominio del calcolabile definito paradigmaticamente da ciò che una macchina di Turing può calcolare . Oltre a ciò esistono altre gerarchie di lingue inclusa la gerarchia aritmetica .

Bibliografia

• Noam Chomsky,
  • 1959a Su alcune proprietà formali delle grammatiche , Information and Control 2, pp.  137–67 .
  • 1959b Una nota sulle grammatiche della struttura delle frasi , Information and Control 2, pp.  393–95 .
  • 1962 Grammatiche prive di contesto e archiviazione pushdown , RLE Quart.Prog. Rept. n o  65. Cambridge, Mass., MIT.

• John E. Hopcroft e Jeffrey D.Ullman , Introduzione alla teoria, ai linguaggi e al calcolo degli automi , Addison-Wesley ,1979

• (en) John E. Hopcroft , Rajeev Motwani e Jeffrey D.Ullman , Introduzione alla teoria, ai linguaggi e al calcolo degli automi , Addison-Wesley ,2007, 3 e  ed. ( ISBN  978-0-32146225-1 )

• Daniel IA Cohen , Introduzione alla teoria del computer , John Wiley & Sons ,1997
• Peter Linz, Introduzione ai linguaggi formali e agli automi , Jones e Bartlett,2001, 3 e  ed. , 410  p. ( ISBN  978-0-7637-1422-2 , leggi online )

Note e riferimenti

1. (in) Noam Chomsky , "  Tre modelli per la descrizione del linguaggio  " , IRE Transactions on Information Theory , n o  21956, p.  113–124 ( leggi in linea ).
2. Cohen 1997 , cap. 30: La Gerarchia di Chomsky .
3. Hopcroft e Ullman 1979 , cap. 9: La Gerarchia di Chomsky . La ristampa di quest'opera nel 2001 con Rajeev Motwani non include più questo capitolo.
4. Linz 2001 , Cap. 11.4: La Gerarchia di Chomsky .
5. Hopcroft e Ullman 1979 , cap. 10: Linguaggi deterministici privi di contesto .
6. AK Joshi, LS Levy e M. Takahashi, "Tree adjunct grammars", Journal of Computer Systems Science , 10 (1), 1975.
7. Grammatiche adiacenti ad albero basato sull'unificazione .
8. (in) K. Vijay-Shanker , "  A Study of Tree-Adjoining Grammars  " , PhD Thesis , University of Pennsylvania ,Gennaio 1988.
9. vedi anche: Robert McNaughton, “ Un inserimento nella gerarchia di Chomsky? ", Jewels are forever , 1999, pagine 204-212, e T. Jurdziński, K. Lorys, G. Niemann, F. Otto," Alcuni risultati sugli automi RWW e RRWW e la loro relazione con la classe del contesto in crescita- lingue sensibili ", Journal of Automata, Languages ​​and Combinatorics , Volume 9 Number 4, ottobre 2004.

Articoli Correlati

• Teoria degli automi
• Teoria del linguaggio
• Linguaggio formale
• Grammatica formale
• Marcel-Paul Schützenberger

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">