Osma sada domacich uloh

Uloha 1

Je Postov korespondencny problem nerozhodnutelny aj v pripade, ze slova xi a yi su nad jednopismenovou abecedou?

Uloha 2

Su dane dva homomorfizmy h1 a h2 z abecedy Sigma1 do Sigma2. Je rozhodnutelny problem, ci pre h1 a h2 existuje take slovo w, ze h1(w) = h2(w)?

Uloha 3

Je dana n-tica slov x1,x2, ..., xn a bezkontextova gramatika G. Zistite, ci je rozhodnutelne, ci existuej postupnost indexov i1, i2, ..., ik takych, ze slovo xi1xi2...xik patri do jazyka L(G).

Uloha 4

Dokazte, ze neexistuje algoritmus, ktory pre lubovolny TS rozhodne, ci tento stroj akceptuje nejake slovo obsahujuce podslovo aba.

Uloha 5

Dany je TS A. L3A je mnozina vsetkych slov nad abecedou Sigma, ktore obsahuju podslovo u dlzky 3, ktore je podslovom nejakeho slova z L(A).

Dokazte, ze L3A je regularny jazyk.

Uloha 6

Zabudnite, ze viete, co to je PKP. Viete, ze prazdnost RE jazykov je nerozhodnutelny problem. Dokazte, ze prazdnost prieniku bezkontextovych jazykov je nerozhodnutelna.

Uloha 7

Zabudnite, ze viete, co to je PKP. Viete, ze prazdnost RE jazykov je nerozhodnutelny problem. Dokazte, ze rovnost Sigma* pre bezkontextove jazykoy je nerozhodnutelna.