Chomského hierarchie: Porovnání verzí
Smazaný obsah Přidaný obsah
m {{Formální jazyky a gramatiky}} |
Bez shrnutí editace |
||
Řádek 16:
:Generují [[regulární jazyk|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 ř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]].
Přičemž platí, ž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.
{{Formální jazyky a gramatiky}}
| |||