Chomského hierarchie

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 (frázové/neomezené gramatiky)
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. V případě, že je jazyk generován úplným Turingovým strojem ( Turingův stroj akceptuje nebo zamítá), je tento jazyk nazýván jako rekurzivní.

Gramatiky typu 1 (kontextové gramatiky, Context-sensitive, CSG)
Generují kontextové jazyky. Tyto gramatiky se skládají z pravidel , kde  je neterminál  a  jsou řetězce terminálů a neterminálů, přičemž  je neprázdný ( a  prázdné být mohou). Pravidlo  je povoleno, pokud se  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 řetězcem terminálů a neterminálů . Tyto jazyky jsou právě jazyky rozpoznatelné nějakým nedeterministickým zásobníkovým automatem.

Upřesnění: Gramatiky typu 2 mohou obsahovat  pravidla. Přesto jsou jimi generované jazyky podmnožinou jazyků generovaných gramatikami typu 1, protože existuje algoritmus na převod libovolné gramatiky typu 2 na gramatiku bez  pravidel.

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 terminálu, který může být následován jedním neterminálem (tedy pravidla  a , kde ). Tyto gramatiky se také nazývají pravolineární. Obdobně se definují i levolineární gramatiky, kde může být na pravé straně pravidel jeden terminál předcházen jedním neterminálem. Nikdy se však nesmí vyskytovat v jedné gramatice zároveň pravidla jak z pravolineární gramatiky, tak z levolineární. Pravé lineární gramatiky a levé lineární gramatiky jsou ekvivalentní. Pravidlo  je povoleno, pokud se  nevyskytuje na pravé straně žádného pravidla. Tyto jazyky jsou právě jazyky rozpoznatelné konečným automatem.

Hierarchie 
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. Jedná se zde vždy o vlastní podmnožiny, tj. 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í.

Mezivrstvy 
Kromě zmíněných čtyř typů gramatiky jsou i mezivrstvy. Pro přirozené jazyky se obvykle používají gramatiky, jejichž vyjadřovací síla je mezi gramatikami typu 1 a 2. Kategorie nese název gramatika spojování stromů (tree-adjoining grammar). Švýcarská němčina však spadá do vrstvy kontextové gramatiky.

Poznámka: Lidé často z faktu, že například třída regulárních jazyků je „menší“ než třída bezkontextových jazyků, vyvozují, že totéž platí i pro jazyky, tedy že regulární jazyky jsou „menší“ než bezkontextové jazyky. Tato představa je mylná; největší jazyk nad libovolnou abecedou (množina všech řetězců nad touto abecedou) je regulární jazyk, čili patří do „nejmenší“ z uvedených tříd. Lepší je představa, že zatímco regulární jazyky „vysekávají“ z množiny všech řetězců jazyky dosti hrubě, bezkontextové jazyky jemněji, kontextové ještě jemněji, atd. Například ve snaze přiblížit se kontextovému jazyku  lze sestrojit regulární jazyk, kde počet symbolů , ,  je stejný pouze do 1000 symbolů, tj. jazyk  nebo bezkontextový jazyk, který obsahuje pouze ta slova z , která obsahují stejně symbolů  jako ,  jako  nebo  jako .

Odkazy

Poznámky

Reference

Literatura

Související články 
 Formální gramatika
 Terminální a neterminální symbol

Formální jazyky