Chomského hierarchie: Porovnání verzí

'''Chomského hierarchie''' je hierarchie tříd [[formální gramatika|formálních gramatik]] generujících [[formální jazyk|formální jazyky]]y. Byla vytvořena [[Noam Chomsky|Noamem Chomskym]] v roce [[1956]].

:Generují [[kontextový jazyk|kontextové jazyky]]. Tyto gramatiky se skládají z pravidel <math>\alpha A\beta \rightarrow \alpha\gamma\beta</math>, kde <math>A</math> je neterminál a <math>\alpha</math>, <math>\beta</math> a <math>\gamma</math> řetězce terminálů a neterminálů. Řetězce <math>\alpha</math> a <math>\beta</math> mohou být prázdné, ale <math>\gamma</math> musí být neprázdná. Pravidlo <math>S \rightarrow \epsilon</math> je povoleno, pokud se <math>S</math> nevyskytuje na pravé straně žádného pravidla. Tyto jazyky jsou právě jazyky rozpoznatelné [[lineárně ohraničený Turingův stroj|lineárně ohraničeným Turingovým strojem]].

:Generují [[regulární jazyk|regulární jazyky]]y. 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 řetězec 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ý automat|konečným automatem]].

[[fa:وراثت چامسکىچامسکی]]