8. Sada domacich uloh

Uloha 1 (prez)

Nech P je program v jazyku Pascal, ktory nacitava vstup z jedineho vstupneho suboru (a nerobi ziadny dalsi vstup/vystup) a r je cislo riadku.

Zistite, ci je rozhodnutelne, ci existuje taky vstupny subor, aby P pri spracovavani tohto vstupu niekedy prisiel na riadok r.

Uloha 2 (prez)

Detailne dokazte, ze problem zastavenia pre LBA je rozhodnutelny.

Uloha 3 (prez)

  1. Dokazte, ze neexistuje algoritmus, ktory pre lubovolny TS rozhodne, ci tento stroj akceptuje nejake slovo obsahujuce podslovo aba.
  2. 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 4 (prez)

  1. Dokazte, ze bezkontextovy jazyk L nad 1-pismenkovou abecedou je regularny
  2. Zistite, ci je rozhodnutelna prazdnost prieniku dvoch bezkontextovych jazykov L1, L2, ak

b.1) L1 je nad jednopismenovou abecedou

b.2) L1 aj L2 su nad jednopismenovou abecedou

 

Uloha 5 (prez)

  1. Je rozhodnutelne, ci pre dane homomorfizmy h1,h2 : Sigma1 -> Sigma2 existuje slovo w take, ze h1(w) = h2(w) ?
  2. Je rozhodnutelne, ci je dana gramatika viacznacna? Viacznacna gramatika je taka, pre ktoru existuje slovo w s dvoma roznymi lavymi krajnymi odvodeniami.

 

Uloha 6 (odovzdavacia)

 Dokazte, ze problem prazdnosti jazyka je pre bezkontextove jazyky rozhodnutelny.

 

Uloha 7

a) Zistite, ci ma PKP riesenie.

u1 = 1011, u2 = 1, u3 = 0, u4 = 111, u5 = 10011,

v1 = 1001, v2 = 1101, v3 = 1, v4 = 1, v5 = 1

 

b) Zistite, ci ma PKP riesenie.

u1 = 11, u2 = 00101, u3 = 101, u4 = 11, u5 = 1011,

v1 = 00101, v2 = 11, v3 = 11, v4 = 011, v5 = 10

 

c) Zostrojte PKP, ktory ma konecne vela rieseni (viac ako 0).