Template:Linguaggi formali e grammatiche

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 sovrastante.