Cesko.wiki Chomského hierarchie
Author
Albert FloresChomské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 Chomským 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. +more 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). +more 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. +more 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ě. +more 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.
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. +more 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. +more 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. +more 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 \le 1000 \land n \in N \} \cup \{ a^{i}b^{j}c^{k} | i > 1000 \land j > 1000 \land k > 1000 \} nebo bezkontextový jazyk, který obsahuje pouze ta slova z L_{R} , která obsahují stejně symbolů a jako b, a jako c nebo b jako c.
