Chomského hierarchie: Porovnání verzí

[[Soubor:Chomskeho_hierarchie.svg|thumbnáhled|Chomského hierarchie tříd jazyků]]

:Generují [[regulární jazyk]]y. 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 <math>A \rightarrow a</math> a <math>A \rightarrow aB</math>, kde <math> a \in \Sigma, A, B \in N</math> ). 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 <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é [[konečný automat|konečným automatem]].