Chomskyn hierarkia

Wikipedia
Loikkaa: valikkoon, hakuun

Chomskyn hierarkia on tunnetuin järjestelmä formaaleja kieliä tuottavien formaalien kielioppien luokittelemiseen. Kieliopit muodostavat järjestelmässä hierarkian, jossa yksinkertaisempi kielioppi on myös yleisemmän luokan mukainen kielioppi.

Hierarkian portaat ovat:

Suomennokset ovat vakiintumattomia.

Chomskyn hierarkia on nimetty sen kehittäjän, amerikkalaisen kielitieteilijän professori Noam Chomskyn mukaan.

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.