Chomského hierarchie

Chomského hierarchie tříd jazyků

Chomského hierarchie je hierarchie tříd formálních gramatik generujících formální jazyky. Byla vytvořena Noamem Chomskym v roce 1956.

Chomského hierarchie se skládá z následujících tříd:

Gramatiky typu 0

Zahrnují v sobě všechny formální gramatiky, generují právě ty jazyky, které mohou být rozpoznané nějakým Turingovým strojem. Tyto jazyky se někdy nazývají rekurzivně spočetné jazyky.

Gramatiky typu 1 (kontextové gramatiky)

Generují kontextové jazyky. Tyto gramatiky se skládají z pravidel , kde A je neterminál a α, β a γ řetězce terminálů a neterminálů. Řetězce α a β mohou být prázdné, ale γ musí být neprázdná. Pravidlo je povoleno, pokud se S nevyskytuje na pravé straně žádného pravidla. Tyto jazyky jsou právě jazyky rozpoznatelné lineárně ohraničeným Turingovým strojem.

Gramatiky typu 2 (bezkontextové gramatiky)

Generují bezkontextové jazyky. Skládají se z pravidel s neterminálem A a řetězcem terminálů a neterminálů γ. Pravidlo je povoleno, pokud se S nevyskytuje na pravé straně žádného pravidla. Tyto jazyky jsou právě jazyky rozpoznatelné nějakým nedeterministickým zásobníkovým automatem.

Gramatiky typu 3 (regulární gramatiky)

Generují regulární jazyky. Pravidla těchto gramatik jsou omezena na jeden neterminál na levé straně. Pravá strana se skládá z řetězce terminálů, který může být následován jedním neterminálem. Tyto gramatiky se také nazývají pravé lineární gramatiky. Obdobně se definují i levé lineární gramatiky, kde může být na pravé straně pravidel řetězec terminálů předcházen jedním neterminálem. Pravé lineární gramatiky a levé lineární gramatiky jsou ekvivalentní. Regulární gramatika je ve standardní formě, pokud je pravá strana tvořena jedním terminálem následovaným jedním neterminálem nebo pokud je pravá strana prázdné slovo. Tyto jazyky jsou právě jazyky rozpoznatelné konečným automatem.

Přičemž platí, že každý regulární jazyk je také bezkontextový, každý bezkontextový jazyk je také kontextový, každý kontextový jazyk je také rekurzivně spočetný – jak je naznačeno na obrázku. Navíc všechny inkluze jsou oprávněné, tedy existují rekurzivně spočetné jazyky, které nejsou rekurzivní, rekurzivní jazyky, které nejsou kontextové, kontextové jazyky, které nejsou bezkontextové a bezkontextové jazyky, které nejsou regulární.