Chomského hierarchie: Porovnání verzí
Smazaný obsah Přidaný obsah
m r2.7.2) (Robot: Přidávám la:Hierarchia Chomskiana |
opravena chyba, která jasně vyplývá z dalšího textu a přímo z části věnované pouze regulárním gramatikám |
||
Řádek 16:
;Gramatiky typu 3 ([[Regulární gramatika|regulární gramatiky]])
:Generují [[regulární jazyk]]y. Pravidla těchto gramatik jsou omezena na jeden neterminál na levé straně. Pravá strana se skládá z
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. Jedná se zde vždy o vlastní podmnožiny, tj. existují rekurzivně spočetné jazyky, které nejsou rekurzivní, rekurzivní jazyky, které nejsou kontextové, kontextové jazyky, které nejsou bezkontextové a bezkontextové jazyky, které nejsou regulární.
|