10. Sada domacich uloh

Uloha 1 (prez)

Dany je TS A so stavmi (q0,q1,q2,qF) s paskovou abecedou {a,b,c} 
(BL je blank) pociatocnym stavom q0 a akceptacnym qF.

delta(q0,a)  = (q1,c,1)
delta(q0,c)  = (q0,c,1)
delta(q0,BL) = (qF,BL,0)
delta(q1,x)  = (q1,x,1)  pre x = a,c
delta(q1,b)  = (q2,c,-1)
delta(q2,x)  = (q1,x,-1) pre x = a,c
delta(q2,BL) = (q0,BL,1)

Napiste delta fciu pre cast automatu A', ktory simuluje A na skomprimovanej
paske (staci komprimacia 2 policok do jedneho). Pouzite konstrukciu z vety o
zrychlovani (nemusite pisat kod pre samotnu komprimaciu). Tento automat sice
nebude pracovat rychlejsie ako povodny, ale pre vyssiu komprimaciu by bola
jeho delta fcia prilis dlha.

Uloha 2 (prez)

Majme orientovany graf G, ktoreho pocet vrcholov nie je dopredu znamy. Nech TS A akceptuje jazyk

L = {u#v | u,v su binarne zapisy cisel vrcholov, z u do v vedie v G hrana}

Pre dany kod stroja A: Je rozhodnutelne, ci v G vedie z vrchola 0 do vrchola 1 cesta?

Uloha 3

Je nasledujuci problem rozhodnutelny?
"Pre dany TS A, slovo w  a stavy p1,p2,p3: prejde A pri vypocte na w 
niekedy postupnostou stavov p1,p2,p3?"

Uloha 4

Majme triedu TS, ktore nemaju viac ako dva stavy. Je pre tuto triedu
rozhodnutelny problem
"Pre dany TS A a slovo w, patri w do L(A)?"

Uloha 5 (odovzdavacia)

Zistite ci je trieda DSPACE(n2) uzavreta na homomorfizmus. Svoje tvrdenie dokazte.