Dvanasta sada domacich uloh
Dolezita poznamka k uloham 1 a 2: Pravom mate pocit, ze ste tie ulohy uz
niekde videli. Vludila sa nam chyba do definicie operacie minima jazyka -
to, co sme definovali v 11. sade sa vola maximum jazyka.
Uloha 1
Dokazte alebo vyvratte: deterministicke bezkontextove jazyky su uzavrete
na operaciu minima jazyka.
Jazyk L' je minimum jazyka L, ak L' obsahuje vsetky
slova w z jazyka L, ktorych ziaden prefix nepatri do jazyka
L.
Uloha 2
(pre fajnsmekrov :) )
Dokazte alebo vyvratte: bezkontextove jazyky su uzavrete
na operaciu minima jazyka. (definicia vid. predch. uloha)
Uloha 3
Dany je lubovolny nedeterministicky turingov stroj A slabo casovo
ohraniceny funkciou n2 (t.j. pre kazde slovo w
dlzky n z jazyka
L(A) existuje vypocet dlzky najviac n2). Zostrojte ekvivalentny deterministicky turingov stroj
A', ktory prehlava strom konfiguracii stroja A do hlbky. (V
konstrukcii z prednasky pouziva DTS prehladavanie do sirky.)
Uloha 4
Zostrojte deterministicky Turingov stroj s neprepisovatelnou vstupnou
paskou a jedinou pracovnou paskou, ktory pre vstup w dlzky
n>1 na pracovnej paske oznaci hornu celu cast
log2 n znakov. Za oznacene sa povazuje kazde
policko, na ktorom nie je blank (TS nemoze zapisovat blanky).
Uloha 5
Zostrojte turingov stroj, ktory na lubovolnom vstupe dlzky n urobi
f(n)
krokov, kde f(n) = Theta(n log n), a zastavi.
Uloha 6
Definujme triedu DEXP ako zjednotenie tried
DTIME(cn), kde c ide od 1 po nekonecno.
Dokazte, ze trieda NSPACE(n) je podmnozinou triedy DEXP.
Uloha 7
Ukazte, ze jazyk { wcw | w patri do {a,b}* } patri do triedy
DSPACE(log n).