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 --> 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
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
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.
|