Prva sada domacich uloh
Vseobecne upozornenie: Ak bola odprednasana vseobecna konstrukcia na
riesenie danej ulohy, pouzivajte ju.
Uloha 1
Dokazte alebo vyvratte: Trieda regularnych jazykov je uzavreta na inverznu
(regularnu) substituciu.
Uloha 2
Dokazte alebo vyvratte: Trieda bezkontextovych jazykov je uzavreta na
inverznu (bezkontextovu) substituciu.
Uloha 3
Definujme operaciu cyklickeho posunu:
cykl(L) = { uv | vu patri do L }
Dokazte alebo vyvratte: Trieda regularnych jazykov je uzavreta na cyklicky
posun.
V ulohach 4-7 zostrojte a-prekladac, ktory zobrazi jazyk L1 na
jazyk L2:
Uloha 4
L1 = { anbanban | n >= 0 }
L2 = { anbncn | n >= 0 }
Uloha 5
L1 = { w | pocet a vo w = pocet b vo w = pocet c vo w }
L2 = { anbncn | n >= 0 }
(Oba jazyky nad abecedou {a,b,c})
Uloha 6
L1 je lubovolny jazyk a
L2 = h-1(L1), kde h
je nejaky dany homomorfizmus.
Uloha 7
L1 = mnozina syntakticky korektnych pascalovskych programov
L2 = { ww | w je nad abecedou {a,b,c} }
Uloha 8
Dokazte, ze a-prekladace, ktore maju druhu a tretiu zlozku delta funkcie
dlzky najviac jeden su normalnym tvarom pre a-prekladace.
Uloha 9
Dokazte alebo vyvratte: a-prekladace su uzavrete na operaciu kompozicie.
To znamena, ze pre lubovolne a-prekladace
A1 a A2 existuje a-prekladac A taky, ze pre lubovolny
jazyk L dostaneme zhodny vysledok, ak ho prelozime najprv prekladacom
A1 a potom A2, ako keby sme ho prelozili len prekladacom
A.