Gerarchia di Chomsky: differenze tra le versioni

 

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

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

 

Quella seguente è una semplice grammatica che definisce un linguaggio simile:

Simboli terminali <math>\{p, q\}</math>, simboli non terminali <math>\{S\}</math>, simbolo iniziale <math>S</math>, regole di produzione

 

== La gerarchia ==

 

La gerarchia di Chomsky è composta dai seguenti livelli:

<references/>

 

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

 

[[en:Chomsky hierarchy]]

[[es:Jerarquía de Chomsky]]

[[fi:Chomskyn hierarkia]]

[[fr:Hiérarchie de Chomsky]]