Siesta sada domacich uloh

Uloha 1

Dokaz vety z prednasky: Ku kazdemu frazovemu jazyku L existuje kontextovy jazyk L' a homomorfizmus h take, ze L = h(L'). Pre konstrukciu jazyka L' a homomorfizmu h z prednasky detailne dokazte L = h(L').

Uloha 2

Zostrojte Turingov stroj T, ktory bude transformovat kody Turingovych strojov. Na vstupe dostane kod Turingovho stroja <M> a ked skonci, na paske bude kod stroja <M'>, pricom M' akceptuje slovo w prave vtedy, ak M akceptuje slovo rovnakej dlzky ako w, skladajuce sa len zo znakov 1.

Uloha 3

Dany je pripad Postovho korespondencneho problemu, zistite, ci ma riesenie. (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 tehliciek, horny riadok x_i, dolny y_i)

Uloha 4

Dany je pripad modifikovaneho Postovho korespondencneho problemu. Zostrojte pripad Postovho korespondencneho problemu, ktory ma riesenie prave vtedy, ak ma prislusny modifikovany problem riesenie. Pouzite vseobecnu konstrukciu (t.j. tu z prednasky, alebo vlastnu + dokaz)

aba   aa   a    bb
a     b    aa   ba

(tehlicky su cislovane zlava, t.j. (aba,a) musi byt v MPKP prva)

Uloha 5

( pre fajnsmekrov :) )
Dany je neorientovany graf (bez nasobnych hran a sluciek) G=(V,E). Pre tento graf zostrojte instanciu Postovho korespondencneho problemu, ktora ma riesenie prave vtedy, ked v grafe G existuje hamiltonovska cesta. (Hamiltonovska cesta je postupnost vrcholov, v ktorej sa kazdy vrchol nachadza prave raz a kazde dva nasledujuce vrcholy su spojene hranou). Pri konstrukcii by ste sa nemali pokusat tuto cestu hladat. (Kto by rad prisnejsiu specifikaciu: najdite polynomialny algoritmus, ktory pre dany graf vygeneruje prislusnu instanciu PKP).