Pokiaľ nie je povedané ináč, všetky jazyky, gramatiky a automaty v zadaniach sú všeobecné (t.j. môžu byť ľubovoľné). Pokiaľ bola odprednášaná štandardná konštrukcia, používajte ju! V opačnom prípade musíte dokázať správnosť svojej konštrukcie. V zadaní úlohy, ktorú chcete odovzdať ako "veľkú" prezentáciu si slovo zdôvodnite nahraďte slovom dokážte.

Znakom C označujeme cent a znakom S dolár.

1. Zostrojte LBA, ktorý bude akceptovať jazyk:
   L = { a^p | p je prvočíslo}
   Zdôvodnite správnosť svojej konštrukcie.
2. Dokážte, pomocou gramatík, že trieda L_(E)CS je uzavretá na zreťazenie.
3. Dokážte, pomocou gramatík, že trieda L_(E)CS je uzavretá na kladnú iteráciu.
4. Dokážte, pomocou LBA, že trieda L_(E)CS je uzavretá na kladnú iteráciu.
5. Dokážte, že trieda L_(E)CS je uzavretá na inverzný homomorfizmus.
6. Zostrojte LBA, ktorý začne pracovať v konfigurácii CqaⁿS a na páske postupne vytvorí všetky slová dlžky n v abecede {a,b} v lexikografickom usporiadaní. Teda slová w_i, ktoré boli na páske v okamihoch, keď bol automat v stave q_x musia byť v lexikografickom usporiadaní a musia to byť práve všetky slová dlžky n nad abecedou {a,b}.
7. Definujte nedeterministický TS (napíšte formálne 4 definície z prednášky).
8. Dokážte, že Turingov stroj, ktorý má len jednosmerne nekonečnú pásku (má ľavý koncový znak C) je rovnako silný ako štandardný Turingov stroj.