Chomského hierarchie: Porovnání verzí
Smazaný obsah Přidaný obsah
Opraveny třídy 1, 2 a 3 značka: editace z Vizuálního editoru |
Téže v některých zdrojích Jan Holub uvádí, že se gramatiky typu 0 nazývají neomezené, jelikož jsou to gramatiky, které odpovídají obecné definici gramatiky. značka: editace z Vizuálního editoru |
||
Řádek 4:
Chomského hierarchie se skládá z následujících tříd:
;Gramatiky typu 0 (frázové/neomezené gramatiky)
:Zahrnují v sobě všechny formální gramatiky, generují právě ty jazyky, které mohou být rozpoznané nějakým [[Turingův stroj|Turingovým strojem]]. Tyto jazyky se někdy nazývají [[Rekurzivně spočetný jazyk|rekurzivně spočetné jazyky]]. V případě, že je jazyk generován úplným Turingovým strojem (<math>\forall w \in \Sigma^*</math> Turingův stroj akceptuje nebo zamítá), je tento jazyk nazýván jako [[Rekurzivní jazyk|rekurzivní]].
| |||