A Chomsky féle hierarchia

Nyelvtanok:

N. Chomsky annak idején a generatív nyelvtanokat négy csoportba osztotta a felhasznált szabályok formája alapján.

Ezek a következők.

3. típusú nyelvtanok (reguláris nyelvtanok)

    A szabályok alakja lehet

      A --> aB,

      A --> a,

      A --> epszilon, (``epszilon'' az üres szó)

    ahol A, B nemterminálisok, a terminális szmbólum.

2. típusú nyelvtanok (környezetfüggetlen nyelvtanok)

    A szabályok alakja lehet

      A --> alfa,

    ahol A nemterminális, alfa egy nemterminálisokból és terminálisokból álló, akár üres, szó.

1. típusú nyelvtanok (környezetfüggő nyelvtanok)

    A szabályok alakjának kétféle leírása létezik.

    (a) leírás

      béta A gamma --> béta alfa gamma,

      ahol A nemterminális, alfa egy nemterminálisokból és terminálisokból álló, akár üres szó, béta, gamma nemterminálisokból és terminálisokból álló szavak.

    (b) leírás

      alfa --> béta,

      ahol alfa, béta nemterminálisokból és terminálisokból álló nemüres szó, alfa tartalmaz legalább egy nemterminális szimbólumot, és béta hossza legalább akkora, mint alfa hossza. Ezenkívül szereplehet még az

      S --> epszilon, (``epszilon'' az üres szó)

      alakú szabály, ahol S a kezdőszimbólumot jelenti, amely ilyenkor egyetlen szabály jobboldalában sem szerepelhet.

0. típusú nyelvtanok (rekurzíve felsorolható nyelvtanok)

    A szabályok alakja lehet

      alfa --> béta,

    ahol alfa, béta nemterminálisokból és terminálisokból álló szavak, és alfa tartalmaz legalább egy nemterminális szimbólumot.


Vegyük észre, hogy a 0. típus definíciója magába foglalja az összes többit, az 1. típus definíciója (legalaábbis az (a) leírás) 2. és 3. típust, a 2. típus definíciója a 3. típust. A nyelvtanokat tehát ez az osztályozás egymást sorban tartalmazó osztályokba sorolja, legszűkebb a 3., legtágabb a 0. osztály.

Nyelvek:

A nyelvtanok fenti osztályozása alapján a generatív nyelvek is osztályozhatók: i típusúnak mondunk egy nyelvet, ha generálható i típusú nyelvtannal. Később látni fogjuk, hogy hasonlóan a nyelvtanok osztályaihoz, a nyelvek is egymást sorban tartalmazó osztályokat alkotnak, legszűkebb a 3. típusú, azaz reguláris nyelvek osztálya, legtágabb a 0. típusú, azaz rekurzíve felsorolható nyelvek osztálya.