Osma sada domacich uloh
Ulohy 4 a 10 su urcene na odovzdavanie a nie je mozne ich prezentovat.
Odovzdavajte ich do stredy 17.11. 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.
Ulohy 1-6:
Zostrojte zasobnikove automaty (PDA) pre jazyky:
Uloha 1
L = { w | vo w je rovnaky pocet pismen a a pocet pismen
b }
nad abecedou {a,b}
Uloha 2
L = { u | u = wwR, kde w je slovo nad {a,b} }
Uloha 3
L = { uai+jbicjv | uv = wwR, kde
w je slovo nad abecedou {a,b,c} }
Uloha 4
(* odovzdavacia uloha)
L = { aibjck | neplati i=j=k }
Uloha 5
L = { w | w je regularny vyraz }
nad abecedou {a,b,+,.,(,),*}
Uloha 6
L = { w | vo w je pocet pismen a rovny suctu poctu
pismen b a c, pricom pocet pismen c je parny }
nad abecedou {a,b,c}
Uloha 7
Dokazte, ze trieda jazykov akceptovanych
zasobnikovymi automat mi je uzavreta na zretazenie.
(Teda pre dane dva PDA A1 a A2 ukazte, ze existuje PDA
A akceptujuci jazyk L(A1)L(A2).)
Uloha 8
Dokazte, ze trieda bezkontextovych jazykov je uzavreta na operaciu reverz.
(Teda pre bezkontextovy jazyk L dokazte, ze jazyk LR je
bezkontextovy.)
Uloha 9
Dane su jazyky L1 a L2. Definujme operaciu Shuffle:
Shuffle(L1,L2) = { w | existuje n take, ze:
w =
u1v1u2v2...unvn,
kde u1...un je slovo z L1 a
v1...vn je slovo z L2},
pricom ui, vi su slova.
Dokazte, ze ak su jazyky L1 a L2 regularne,
tak aj jazyk Shuffle(L1, L2) je regularny.
Uloha 10
(* odovzdavacia uloha)
Dokazte, ze trieda regularnych jazykov je uzavreta na inverzny homomorfizmus.
(Teda pre lubovolny regularny jazyk L dokazte, ze jazyk h-1(L)
je regularny.)
Uloha 11
Definujme operaciu "polovica jazyka" L:
L1/2 = { w | existuje slovo v take, ze |w| =
|v| a wv patri do L }
Dokazte, ze ak L je regularny jazyk, tak aj jazyk L1/2 je
regularny.