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

=== Mezivrstvy === Kromě zmíněných čtyř typů gramatiky jsou i mezivrstvy. Přirozený jazyk zatím spadá do vrstvy mezi kategorii kontextové a bezkontextové gramatiky. +more Kategorie nese název gramatika spojování stromů (tree-adjoining grammar). Švýcarská němčina však spadá do vrstvy kontextové gramatiky.

=== Doplnění === 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. +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í.

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

Odkazy

Kategorie:Formální jazyky