Vo všetkých úlohách predpokladajte (pokiaľ nie je uvedené ináč), že L, L₁, L₂, atď. sú ľubovoľné jazyky a h je ľubovoľný homomorfizmus. Zjednotenie značíme u, prienik ^, doplnok ^C, a reverz ^R. Nerovnosť značíme !=.

1. Daný je (det. alebo nedet.) TS A, zostrojte NTS A' taký, že L(A')=(L(A))^R
2. Zostrojte TS A taký, že
   L(A)={w | w patrí do {a,b,c}^*, #_a(w)=2#_b(w)=3#_c(w) }
3. Daný je (det. alebo nedet.) TS A, zostrojte NTS A' taký, že L(A')=(L(A))²
4. Daný je homomorfizmus h, zostrojte NTS A taký, že keď na vstupe dostane ľubovoľné slovo w, prepíše ho na h(w) a akceptuje. (Samozrejme h(w) by malo byť zapísané na súvislom úseku pásky, pričom na každom políčku tohoto úseku by malo byť práve 1 písmeno.)
5. Definujte (štandardné 4 definície) Turingov stroj, ktorého páska je nekonečná len smerom doprava, t.j. má ľavý koniec. Ukážte všeoecnú konštrukciu, ako zostrojiť k obyčajnému TS ekvivalentný s takouto páskou.
6. Ukážte, že ku každému NTS A existuje ekvivalentný, ktorý má len jeden akceptačný stav, akonáhle dosiahne akc. stav zastaví sa a ak neakceptuje, tak nikdy neskončí (t.j. nemôže sa zaseknúť a neakceptovať).
7. Zostrojte NTS A, ktorý keď spustíme na prázdnej páske, tak bude pracovať do nekonečna a postupne na pásku písať zápisy prirodzených čísel v dvojkovej sústave, oddelené znakmi #. (T.j. po dosť veľa krokoch bude začiatok popísanej časti pásky vyzerať: 0#1#10#11#100#101#...)
8. Ako by sa zmenila sila NTS, ak by sme dovolili, aby:
   a) mal nekonečnú (spočítateľne veľkú) delta-funkciu
   b) mal nekonečné (spočítateľne veľké) delta-funkciu a množinu stavov, pričom delta funkcia z každého stavu musí byť konečná a akc. stavov musí byť konečne veľa
   c) mal nekonečné (spočítateľne veľké) delta-funkciu a pracovnú abecedu, pričom delta funkcia na každé písmenko musí byť konečná
   d) mohol hýbať hlavou o ľubovoľne veľa políčok v jednom kroku (t.j. pohybová zložka delta-funkcie nebude z {-1,0,1} ale zo Z)
9. Navrhnite spôsob kódovania frázových gramatík s T={a,b} do slov nad vami zvolenou abecedou. (Abecedu si volíte pevne, t.j. pred tým, ako dostanete gramatiku na zakódovanie. Nemôžete ju meniť podľa počtu neterminálov a typu gramatiky.) Zostrojte TS, ktorý bude akceptovať práve vtedy, ak dostane na vstupe váš kód nejakej regulárnej gramatiky.
   Hint: Kódovanie navrhnite tak, aby ste s písaním TS mali čo najmenej roboty.