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. Vieme, že PKP aj MPKP sú nerozhodnuteľné. Je nerozhodnuteľná aj nasledujúca modifikácia? Máme N typov domín, x_i, y_i je z {a,b}^*, chceme vedieť, či sa dajú poskladať tak, aby horné a dolné slovo boli rovnako dlhé a líšili sa na max. 2 miestach. Zdôvodnite správnosť svojho riešenia.
2. Definujte (štandartné 4 definicie) nedeterministický Turingov stroj so skutočnou páskou. Takýto stroj bude mať 2 špeciálne symboly B (blank) a X (machuľa), pričom:
   • B môže len čítať
   • ak bol na políčku B, moze tam zapisať ľubovoľný znak z Gamma
   • ak bol na políčku znak z Gamma, môže tam zapisať bud ten istý znak, alebo už len X (t.j. nemôže ho prepisať iným znakom z Gamma)
   • ak je na políčku X, môže tam zapisať už len X
   Neformálne zdôvodnite silu vami definovaného stroja.
3. Je rozhodnuteľné, či pre dané homomorfizmy h₁, h₂ : Sigma₁ -> Sigma₂ existuje slovo w také, že h₁(w) = h₂(w) ? Zdôvodnite správnosť svojho riešenia.
4. Je daný Turingov stroj A, jeho stav q a vstupné slovo w. Je rozhodnuteľné, či sa A pri výpočte na slove w dostane do stavu q? Dokážte alebo vyvráťte.
5. Je daná n-tica slov x₁,x₂, ..., x_n a bezkontextová gramatika G. Zistite, či je rozhodnuteľné, či existuje postupnosť indexov i₁, i₂, ..., i_k takých, že slovo x_i1x_i2...x_ik patrí do jazyka L(G). Zdôvodnite správnosť svojho riešenia.
6. Daný je TS A. L_3A je množina všetkých slov nad abecedou Sigma, ktoré obsahujú podslovo u dlžky 3, ktoré je podslovom nejakého slova z L(A). Dokážte, že L_3A je regulárny jazyk.
7. Zabudnite, že viete, čo to je PKP. Viete, že prázdnosť L_RE je nerozhodnuteľny problém. Dokážte, ze prázdnosť prieniku bezkontextových jazykov je nerozhodnuteľná.