Tretia sada domacich uloh

Pred tym, ako si rezervujete nejaku domacu ulohu, precitajte si pravidla rezervovania domacich uloh.

Vseobecne upozornenie: Ak bola odprednasana vseobecna konstrukcia na riesenie danej ulohy, pouzivajte ju.
V ulohach 1 a 2 dokazte, ze trieda jazykov akceptovanych LBA je uzavreta na operaciu zretazenia.

Uloha 1

V dokaze pouzite konstrukciu pomocou automatov.

Uloha 2

V dokaze pouzite konstrukciu pomocou gramatik.
V ulohach 3 - 5 zostrojte linearne ohraniceny automat (LBA) akceptujuci dany jazyk.

Uloha 3

L = { aibjci.j | i,j >= 0 }

Uloha 4

L = { ap | p je prvocislo }

Uloha 5

L = { w | w = ai1bj1#ai2bj2# ... aipbjp##aibj,
      p,i,j,ik,jk >= 0 pre k=1,2,...,p,
      slovo w oznacuje orientovany graf taky, ze z vrchola ik vedie hrana
      do vrchola jk a z vrchola i do vrchola j vedie (orientovana) cesta }

Uloha 6

Predpokladajme, ze LBA A ma na paske slovo w = u1cu2c ... c uk nad abecedou {a,b,c}, ui je nad abecedou {a,b}, a je v stave p1. Napiste usek delta-funkcie LBA A taky, ze po jeho vykonani bude A v stave p2 a na paske bude slovo v = u1u2 ... uk c k-1.
(Suvis s prednaskou: Znaky c su biele znaky a automat ma "upratat" pasku.)

Uloha 7

Zostrojte LBA A nad abecedou {a,b}, ktory bude postupne generovat vsetky slova dlzky n v lexikografickom poradi (n je dlzka vstupneho slova). Vygenerovane slovo sa "pocita", ak je A v stave qslovo. Presnejsie, nech wi je slovo na paske v okamihu, ked je A i-ty raz v stave qslovo. Pre kazde i musi platit, ze slovo wi (dlzky n) je v lexikografickom (abecednom) usporiadani pred wi+1. Zaroven sa kazde n-pismenove slovo musi medzi slovami wi nachadzat.

Uloha 8

Dokazte, ze trieda jazykov akceptovanych deterministickymi LBA (DLBA) je uzavreta na operaciu zretazenia.