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 (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 ($\forall w\in \Sigma ^{*}$ 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 $\alpha A\beta \rightarrow \alpha \gamma \beta$, kde $A$ je neterminál $\alpha ,\beta$ a $\gamma$ jsou řetězce terminálů a neterminálů, přičemž $\gamma$ je neprázdný ($\alpha$ a $\beta$ prázdné být mohou). Pravidlo $S\rightarrow \epsilon$ 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 $A\rightarrow \gamma$ s neterminálem $A$ a řetězcem terminálů a neterminálů $\gamma$. 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 $\epsilon$ 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 $\epsilon$ 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\rightarrow a$ a $A\rightarrow aB$, kde $a\in \Sigma ,A,B\in N$ ). 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 $S\rightarrow \epsilon$ je povoleno, pokud se $S$ nevyskytuje na pravé straně žádného pravidla. 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. 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í.

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 $L=\{a^{n}b^{n}c^{n};n\in N\}$ lze sestrojit regulární jazyk, kde počet symbolů $a$, $b$, $c$ je stejný pouze do 1000 symbolů, tj. jazyk $L_{R}=\{a^{n}b^{n}c^{n}|n\leq 1000\land n\in N\}\cup \{a^{i}b^{j}c^{k}|i>1000\land j>1000\land k>1000\}$ a bezkontextový jazyk, který obsahuje pouze ta slova z $L_{R}$, která obsahují stejně symbolů $a$ jako $b$, $a$ jako $c$ nebo $b$ jako $c$.