Le classi di grammatiche di Chmosky e le classi di linguaggi sono:
●
di tipo 0, non limitate
●
di tipo 1, contestuali(context sensitive: CS)
●
di tipo 2, non contestuali(context free: CF)
●
di tipo 3, regolari
Def. Le grammatiche di Chomsky di tipo 0, sono basate sulle produzioni più
generali, del tipo:
α→β , α∈V*°VN°V*, β∈V*
NOTA BENE. Le grammatiche di tipo 0 ammettono anche derivazioni che
accorciano stringhe.
Def. I linguaggi di tipo 0 sono i linguaggi generati da grammatiche di tipo 0.
Def. Le grammatiche di Chomsky di tipo 1, (dette context sensitive o
contestuali) sono basate su produzioni del tipo:
α→β , α∈V*°VN°V*, β∈V+ con |α|≤|β|
Def. I linguaggi di tipo 1 (context sensitive o contestuali) sono i linguaggi
generati da grammatiche di tipo 1.
Def. Le grammatiche di Chomsky di tipo 2, (dette context free o non
contestuali) sono basate su produzioni del tipo: A→β , A∈VN, β∈V+
Def. I linguaggi di tipo 2 (context free o non contestuali) sono i linguaggi
generati da grammatiche di tipo 2.
Perché le grammatiche di tipo 1 sono chiamate contestuali e quelle di tipo 2 non
contestuali?
Nell'originaria formulazione data da Chomsky le grammatiche di tipo 1 sono
51