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. Daný je prípad Postovho korešpondenčného problému, zistite, či má riešenie. (abeceda {0,1,#})

   #000      #
   #      111#
   
   000  000  000  001  001  001  010  010  010  011  011  011  
   011  101  110  010  100  111  001  111  100  000  110  101
   
   100  100  100  101  101  101  110  110  110  111  111  111  
   111  001  010  110  000  011  101  011  000  100  010  001
   

   (spolu 26 tehličiek, horný riadok x_i, dolny y_i)
2. Daný je prípad modifikovaného Postovho korešpondenčného problému. Zostrojte prípad Postovho korešpondenčného problému, ktorý má riešenie práve vtedy, ak má príslušný modifikovaný problém riešenie. Použite všeobecnú konštrukciu (t.j. tú z prednášky, alebo vlastnú + dôkaz)

   aba   aa   a    bb
   a     b    aa   ba
   

   (tehličky sú číslované zľava, t.j. (aba,a) musí byť v MPKP prvá)
3. Predpokladajte, že máte daný algoritmus (deterministický TS, ktorý vždy zastaví), ktorý pre ľubovoľnú bezkontextovú gramatiku G₁ a ľubovoľnú regulárnu gramatiku G₂ rozhodne, či L(G₁)=L(G₂). Na základe tohoto algoritmu zostrojte algoritmus pre riešenie Postovho Korešpondenčného Problému.
4. Zostrojte TS, ktorý akceptuje jazyk L:
   L = { w | w je nad {0,1,#} je platným kódom det. Turingovho stroja}
   Použite kódovanie TS z prednášky. Nemusíte písať delta fciu, stačí dostatočne podrobný popis (na takej úrovni, aby bolo jasné, koľko stavov daný stroj má a na čo slúžia)
5. Rozhodnite, či je PKP nad jednopísmenkovou abecedou rozhodnuteľný, ak áno, popíšte algoritmus, ak nie, dokážte.
6. Nájdite algoritmus (t.j. neformálne popíšte deterministický TS), ktorý pre dané kódy TS A, B a slovo w zostrojí TS A' taký, aby:
   - ak w patrí do L(A), L(A')=L(B)
   - ak w nepatrí do L(A), L(A') je prázdny