Malline:Formaalit kielet
| Automaattiteoria: formaalit kielet ja formaalit kieliopit | |||
|---|---|---|---|
| Chomskyn hierarkia |
Kielioppi | Kieli | Tunnistusautomaatti |
| luokka 0 | Rajoittamaton | Rekursiivisesti numeroituva | Turingin kone |
| Rajoittamaton | Rekursiivinen | Totaalinen Turingin kone | |
| luokka 1 | Yhteysherkkä | Yhteysherkkä | Lineaarisesti rajoitettu |
| luokka 2 | Yhteydetön | Yhteydetön | Pinoautomaatti |
| luokka 3 | Säännöllinen | Säännöllinen | Äärellinen |
| Kukin luokka on sen yläpuolisen luokan aito osajoukko. | |||