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

Gramatiky typu 1 (kontextové gramatiky): Generují kontextové jazyky. Tyto gramatiky se skládají z pravidel $\alpha A\beta \rightarrow \alpha\gamma\beta$ , kde $A$ je neterminál a $α$ , $β$ a $γ$ řetězce terminálů a neterminálů. Řetězce $α$ a $β$ mohou být prázdné, ale $γ$ musí být neprázdná. 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 neterminalem $A$ a řetězcem terminálů a neterminálů $γ$ . Pravidlo $S \rightarrow \epsilon$ je povoleno, pokud se $S$ nevyskytuje na pravé straně žádného pravidla. Tyto jazyky jsou právě jazyky rozpoznatelné nějakým nedeterministickým zásobníkovým automatem.

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 řetězce terminálů, který může být následován jedním neterminálem. Tyto gramatiky se také nazývají pravé lineární gramatiky. Obdobně se definují i levé lineární gramatiky, kde může být na pravé straně pravidel řetezec terminálů předcházen jedním neterminálem. Pravé lineární gramatiky a levé lineární gramatiky jsou ekvivalentní. Regulární gramatika je ve standardní formě, pokud je pravá strana tvořena jedním terminálem následovaným jedním neterminálem nebo pokud je pravá strana prázdné slovo. Tyto jazyky jsou právě jazyky rozpoznatelné konečným automatem.