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