Hierarhija Chomskega

Uvod

1. Regularni jeziki ... opisujemo jih z regularnimi izrazi ... realizirano jih s končnimi avtomati (TOR1)
2. Konteksno neodvisni jeziki ... opisujemo jih s konteksno neodvisnimi gramatikami ... realiziramo jih s skladovnimi avtomati (TOR1)
3. Konteksno odvisni jeziki ... opisujemo jih s kontekstno odvisnimi gramatikami ... realiziramo jih z linearno omejenimi avtomati
4. Rekurzivni jeziki ... opisujemo jih z gramatikami brez omejitev (gramatike tipa 0) ... realiziramo jih s Turingovimi stroji, ki se vedno ustavijo
5. Turingovi jeziki ... opisujemo jih z gramatikami brez omejitev (gramatike tipa 0) ... realiziramo jih s Turnigovimi stroji