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:

• Säännölliset kielet (Regular languages), jotka voidaan tunnistaa äärellisillä automaateilla. Yksinkertaisin luokka.
• Yhteydettömät kielet (yhteysriippumattomat tai kontekstittomat kielet, Context-free languages), tunnistamiseen riittää pinoautomaatti.
• Yhteysherkät kielet (kontekstiherkät kielet, Context-sensitive languages), voidaan tunnistaa lineaarisesti rajoitetulla automaatilla.
• Rekursiivisesti numeroituvat kielet (rekursiivisesti lueteltavat kielet tai yleiset kielet, Recursively enumerable languages), voidaan tunnistaa Turingin koneella. Yleisin luokka.

Suomennokset ovat vakiintumattomia.

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

Lähteet

• 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)

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.