Druha sada domacich uloh

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

V ulohach 1 a 2 popiste jazyk generovany danou (bezkontextovou) gramatikou:
Velke pismena su neterminaly, S je pociatocny neterminal, male pismena su terminalne znaky. Znak | oznacuje viacero moznosti, t.j. zapis

A -> Bc | Cd

znamena dve pravidla

A -> Bc 
A -> Cd

Uloha 1

S -> AB | BA
B -> bS | Sb | b
A -> aS | Sa | a

Uloha 2

S -> AB | BA
B -> aS | Sa | A
A -> bS | Sb | B

Uloha 3

(*odovzdavacia uloha) Zostrojte (bezkontextovu) gramatiku (t.j. sadu odvodzovacich pravidiel) pre jazyk

           i     i+j
L = U {a,b} {c,d}

kde U znamena zjednotenie cez vsetky i a j, i,j>=0.
Zdovodnite spravnost konstrukcie. (popis gramatiky a jazyka generovaneho gramatikou vid. cvicenia)

Uloha 4

Na jazykoch zadefinujme operaciu
O(L₁,L₂) = (L₁^*L₂)^*L₂^*

Dokazte, ze tato operacia je komutativna.

Ulohy 5-7:
Je mozne skonstruovat jazyk L' z jazyka L len pomocou konecneho poctu operacii zretazenia, zjednotenia, prieniku, homomorfizmu a inverzneho homomorfizmu? Ak ano, uvedte jednu moznu konstrukciu, ak nie, zdovodnite (dokazte).

Uloha 5

                R
L  = { w | w = w  , w je slovo nad abecedou {a,b} }
                R
L' = { w | w = w  , w je slovo nad abecedou {a,b,c} }

(znak R znaci reverz, t.j. slovo napisane odzadu)

Uloha 6

(*odovzdavacia uloha)

        i i
L  = { a b  | i >=0 }
        i  i  i
L' = { a  b  c  | i >=0 }

Uloha 7

L  = { w | w je slovo nad abecedou {a,b}, v ktorom je rovnako vela a aj b }
        i  j  j  i
L' = { a  b  c  d | i,j >=0 }

Uloha 8

Zostrojte (bezkontextovu) gramatiku pre jazyk L nad abecedou {a,b}. Slovo w patri do jazyka L prave vtedy, ak

v kazdom vlastnom prefixe slova w (vlastny prefix slova w je take podslovo, ktore zacina prvym znakom slova w a je kratsie ako w) je aspon tolko pismen a ako pismen b
slovo w obsahuje viac pismen b ako pismen a

Uloha 9

nech L₁, L₂, ..., L_k su jazyky. Da sa z nich len pomocou operacii zretazenia a iteracie vytvorit jazyk L?
L = (L₁ U L₂ U ... U L_k)^*

(Znak U znaci zjednotenie)