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 zdôvodniť správnosť svojej konštrukcie. V zadaní úlohy, ktorú chcete odovzdať ako "veľkú" prezentáciu si prípadné slovo zdôvodnite nahraďte slovom dokážte.

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

1. Zostrojte automat čo najjednoduchšieho typu (konečný, zásobníkový, LBA, TS), ktorý pre daný vstup v abecede {0,1,#} zistí, či je to "naozajstný" kód TS.
2. Pre daný orientovaný graf X nech kód grafu <X> je postupnosť tvaru 0^i₁1^j₁0^i₂1^j₂...0^i_n1^j_n, kde i_k,j_k>=1, pričom (i₁,j₁), (i₂,j₂),...,(i_n,j_n) je množina orientovaných hrán grafu X a i₁,j₁,...,i_n,j_n sú čísla vrcholov.
   Zostrojte TS pre jazyk
   L_CYK={ < X > | X je graf obsahujúci cyklus}.
3. Pre daný orientovaný graf X nech kód grafu <X> je postupnosť tvaru 0^i₁1^j₁0^i₂1^j₂...0^i_n1^j_n, kde i_k,j_k>=1, pričom (i₁,j₁), (i₂,j₂),...,(i_n,j_n) je množina orientovaných hrán grafu X a i₁,j₁,...,i_n,j_n sú čísla vrcholov.
   Zostrojte TS pre jazyk
   L_HAM={ <X> | X obsahuje Hamiltonovský cyklus}
   (Môžete predpokladať, že v grafe X neexistujú izolované vrcholy, t.j., číslo každého vrcholu sa v kóde grafu X vyskytuje.)
4. Zostrojte TS, ktorý bude pracovať takto:
   Ak na vstupe dostane kód TS <A> (zapísaný v abecede {0,1,#}), tak ho pretransformuje na kód TS <A'>, ktorý z ľubovoľného vstupu w urobí 1w a na tomto novom vstupe začne pracovať ako A.
5. Zostrojte TS, ktorý na vstupe tvaru a^i₁ba^i₂b...a^i_nb vyznačí niektorý úsek s maximálnym počtom a-čok.
   Teda ak i_k je maximalne spomedzi i₁,...,i_n, tak TS na pásku zapíše slovo a^i₁ba^i₂b ... a^i_k-1bc^i_kba^i_k+1b ... a^i_nb a skončí.
6. Zostrojte LBA pre jazyk
   L={a^i₁ba^i₂b...a^i_nb |  i_j>=1, pričom pre nejaké navzájom rôzne j,k platí, že i_j=i_k}.
   Platí L patrí do L_CS-L_CF?
7. Zostrojte automat čo najjednoduchšieho typu pre jazyk L={u#v^R |  u |-_A v}, kde A je daný TS. (Zápis u |-_A v značí, že slová u a v s v relácii kroku odvodenia TS A.)