Kod grafu je slovo w nad abecedou {1,0,#}, take ze w= e1##e2 ##...##en pricom ei je kod hrany, taky ze ei=v1#v2, kde vi je binarne cislo vrcholu.
To jest, kod grafu je zoznam jeho hran (odelenych ##), pricom hrana sa sklada z dvoch vrcholov (oddelnych #).
Pre jazyk L
L = { w | w je kod grafu, ktory obsahuje cyklus }
Zostrojte turingov stroj(TM) M, taky ze L(M) = L. Svoje tvrdenie dokazte.
Definujte viacpaskovy Turingov stroj (TM) a formalne dokazte, ze jednopaskovy Turingov stroj vie odsimulovat viacpaskove TM. Teda, ze pre kazdy k-paskovy TM M, existuje 1-paskovy TM M', taky ze L(M) = L(M').
Zadefinujte viachlavovy TM a dokazte ze je ekvivalentny s jedno hlavovym. Teda ze pre kazdy k-hlavovy TM M, existuje jednohlavovy TM M', taky ze L(M) = L(M').
Ukazte, ze trieda LRE je uzavreta na cyklicky posun Cycle.
Cycle(w) = { w' | take, ze existuje u,v \in \Sigma* pricom uv = w a vu = w' }
Cycle (L) = { w' | take, ze existuje w \in L pricom w' \in Cycle(w) }
Teda formale dokazte, ze pre kazdy L \in LRE existuje TM M, taky ze L(M) = Cycle(L).
Zadefinujte kod, ktorym sa budu kodovat bezkontextove gramatiky na TM. Zostrojte TM M, taky ktory ak dostane na vstup kod gramatiky, prerobi ho na kod gramatiky generujucej reverz.
A jedna lahsia uloha....
Zosrojte TM, ktory zo vstupu w vyrobi na paske slovo w#w. Teda iba skopiruje raz vstupne slovo.
Zadefinujte TM s jednosmerne nekonecnou paskou a dokazte ich ekvivalenciu s klasickou definiciou (obojsmerne nekonecna paska).