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)