navigation
hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
courses:a4m01tal:zkouska-2011-06-16 [2011/06/17 18:28] andelmi2 |
courses:a4m01tal:zkouska-2011-06-16 [2025/01/03 18:28] (aktuální) |
||
|---|---|---|---|
| Řádek 17: | Řádek 17: | ||
| 2) | 2) | ||
| a) Definuj nedeterministický TM. Definuj, co znamená, že tento TM přijímá jazyk L. | a) Definuj nedeterministický TM. Definuj, co znamená, že tento TM přijímá jazyk L. | ||
| - | b) TM přijímající L={w0w | w je binární} Nejprve slovně popiš, pak tabulky nebo přechodový diagram (body jsou i za zprávný popis stroje | + | b) TM přijímající L={w0w | w je binární} Nejprve slovně popiš, pak tabulky nebo přechodový diagram (body jsou i za zprávný popis stroje, klidně i poloviční počet bodů z příkladu) |
| c) Napiš výpočet přijetí slova 11011 | c) Napiš výpočet přijetí slova 11011 | ||
| Řádek 23: | Řádek 23: | ||
| a) Definuj jazyky RP a ZPP. Příklad jazyka RP. | a) Definuj jazyky RP a ZPP. Příklad jazyka RP. | ||
| b) Jaký je vztah mezi jazyky ROZHODOVANÝMI deterministickým TM a jazyky rozhodovanými nedeterministikým TM. | b) Jaký je vztah mezi jazyky ROZHODOVANÝMI deterministickým TM a jazyky rozhodovanými nedeterministikým TM. | ||
| - | c) Co jsou to rekurzivní a rekurzivně spočetné jazyky. | + | c) Třída co-RE je doplněk jazyka RE. Co platí pro třídy R, RE, co-RE a třídu úplně všech jazyků VS. Napiš všechny inkluze, které platí. Pokud jsou některé tyto inkluze ostré, uveď příklad jazyka patřícího do jedné třídy a nepatřícího do druhé. |
| - | d) Vztah mezi NP, rekurzivnými a rekurzivně spočtenými. | + | Možná ještě nějaké body, už si nepvzpomínám |
