Chomskyn hierarkia

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.

LähteetMuokkaa

  • Chomsky, Noam: Three models for the description of language. IRE Transactions on Information Theory, 1956, 2. vsk, nro 3, s. 113–124. Artikkelin verkkoversio.
  • Laitila, Erkki: Symbolic analysis and atomistic model as a basis for a program comprehension methodology. Jyväskylä studies in computing 90. Jyväskylä: University of Jyväskylä, 2008. (englanniksi)