![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/a/a6/Chomskeho_hierarchie.svg/langcs-640px-Chomskeho_hierarchie.svg.png&w=640&q=50)
Chomského hierarchie
hierarchie tříd formálních gramatik generujících formální jazyky / From Wikipedia, the free encyclopedia
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]
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a6/Chomskeho_hierarchie.svg/220px-Chomskeho_hierarchie.svg.png)
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.