definite come quelle grammatiche le cui produzioni hanno la forma:
α → γ con α=φ1Αφ2 e γ=φ1βφ2, e con Α∈VN , φ1,φ2∈V*, β∈V+
Quindi, se |φ1| ≥ 1 o |φ2| ≥ 1, la produzione esprime il fatto che il non terminale
A viene rimpiazzato dalla stringa β solo se appare nel contesto delle stringhe φ1
e φ2. Per tale motivo quelle produzioni (e le relative grammatiche) sono
chiamate "contestuali".
Teorema. Le grammatiche di tipo 1 e le grammatiche contestuali secondo
Chomsky consentono di generare la stessa classe di linguaggi.
Def. Le grammatiche di Chomsky di tipo 3, (dette regolari) sono basate su
produzioni del tipo:
A→aB oppure A→a, con A, B∈VN, a∈VT
Def. I linguaggi di tipo 3 (regolari) sono i linguaggi generati da grammatiche di
tipo 3.
Le grammatiche di tipo 3 vengono chiamate lineari perché nel lato destro di
ogni produzione compare al più un solo non termina