Chomského hierarchie
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.[1]
Chomského hierarchie se skládá z následujících tříd:[2][3][4][pozn. 1]
- 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
editovatPlatí, ž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
editovatKromě 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
editovatPoznámky
editovat- ↑ Různí autoři mohou používat odlišné definice pro jednotlivé typy gramatik; mělo by jít dokázat, že generativní síla gramatiky určitého typu podle alternativní definice je stejná jako podle zde uvedených definic. Někteří autoři se nezabývají tím, zda gramatiky určitého typu jsou schopny vygenerovat prázdné slovo.
Reference
editovat- ↑ Chomsky 1956.
- ↑ Chomsky 1959, s. 141–142.
- ↑ Molnár, Češka a Melichar 1987.
- ↑ Chytil 1984, s. 124.
Literatura
editovat- CHOMSKY, Noam, 1956. Three models for the description of language. IRE Transactions on Information Theory. Roč. 2, čís. 3, s. 113–124. Dostupné v archivu pořízeném z originálu dne 2016-03-07. DOI 10.1109/TIT.1956.1056813.
- CHOMSKY, Noam, 1959. On certain formal properties of grammars. Information and Control 2. S. 137–167. Definice na str. 141–142. Dostupné online.
- MOLNÁR, Ľudovít; ČEŠKA, Milan; MELICHAR, Bořivoj, 1987. Gramatiky a jazyky. Bratislava: Alfa.
- CHYTIL, Michal, 1984. Automaty a gramatiky. Praha: SNTL.