Druha sada domacich uloh

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

Ulohy 1 a 5 su urcene na odovzdavanie a nie je mozne ich prezentovat. Odovzdavajte ich do stredy 23. 2. rana (t.j. 8:10) do skatule na chodbe pred sekretariatom katedry informatiky.

Vseobecne upozornenie: Ak bola odprednasana vseobecna konstrukcia na riesenie danej ulohy, pouzivajte ju.
V ulohach 1 - 4 zostrojte linearne ohraniceny automat (LBA) akceptujuci dany jazyk.

Uloha 1

(*odovzdavacia uloha)
L = { ww | w je slovo nad abecedou {a,b} }

Uloha 2

L = { an2 | n > 0 }

Uloha 3

L = { a2n | n > 0 }

Uloha 4

Nech G je gramatika s pravidlami 
S -> ab | bbA 
A -> aaS | b
Zostrojte linearne ohraniceny automat pre jazyk 
L = { w1#w2# ..#wn | wi =>G wi+1 
      pricom w1 = S a wn neobsahuje neterminaly }
(L je nad abecedou S,A,a,b,#).

Uloha 5

(*odovzdavacia uloha)
Definujte dvojsmerny konecny automat, t.j., konecny automat s moznostou pohybu hlavy aj dolava (standardne 4 definicie).
Mimo bodovania: skuste sa zamysliet nad silou takehoto automatu.

Uloha 6

L1 = { ap | p je prvocislo mensie ako 100 }
L2 = { w | w je nad abecedou {a,b,c} a neobsahuje styri rovnake 
           pismena za sebou }
Zostrojte a-prekladac, ktory prelozi jazyk L1 na jazyk L2.

Uloha 7

Nech R je regularny jazyk. Zostrojte a-prekladac MR taky, ze MR(L) = L ^ R (znak ^ znamena prienik) pre kazdy jazyk L.

Uloha 8

Nech R je binarna relacia na konecnej mnozine (abecede) Sigma. Nech 
L = {a1a2 .. an |  ai R ai+1 pre 0<i<n, 0<n }
Dokazte, ze L je regularny.

Uloha 9

Jazyk regularnych gramatik sa sklada zo slov, ktore su korektnymi zapismi regularnych gramatik pomocou abecedy skladajucej sa zo symbolov {, }, (, ), ->, , (ciarka) a malych a velkych pismen latinskej abecedy. Napriklad gramatika zo 4. ulohy sa v nom zapise ako 
({A,S},{a,b},{S->ab,A->aaS,S->bbA,A->b},S)
Zostrojte linearne ohraniceny automat rozpoznavajuci jazyk regularnych gramatik.

Uloha 10

(Pre fajnsmekrov :)) Rozhodnite, ci je nasledujuci jazyk bezkontextovy: 
L = {aibjck | i != j, j != k a zaroven k != i }