Prva sada domacich uloh
Uloha 1
Nech L1 a L2 su jazyky nad abecedou
{a,b}:
- L1 = { u | slovo u ma dlzku nie vacsiu ako 5
a pocet a v slove u nepresahuje pocet b }
- L2 = { u | slovo u ma dlzku nie vacsiu ako 5
a pocet b v slove u nepresahuje pocet a }
Zistite, kolko slov obsahuje jazyk L1L2.
Uloha 2
Pre lubovolny jazyk L oznacme SigmaL mnozinu vsetkych
pismen, ktore sa skutocne v L vyskytuju (pre kazde pismeno z
SigmaL existuje slovo z L, v ktorom sa toto pismeno
vyskytuje). Mnozinu SigmaL nazveme abecedou jazyka L.
Existuju take jazyky L1 a L2, pre ktore
plati
L1L2 = L2L1, pricom ich
abecedy su aspon dvojpismenove?
Uloha 3
Namiesto znaku ? doplnte niektory zo znakov "rovna sa",
"je podmnozinou" alebo "je nadmnozinou". Svoju odpoved dokazte.
a) h(L1 ^ L2) ? h(L1) ^ h(L2)
b) h(L1 U L2) ? h(L1) U h(L2)
(znak "^", resp. "U" znamena prienik, resp. zjednotenie)
Uloha 4
Namiesto znaku ? doplnte niektory zo znakov "rovna sa",
"je podmnozinou" alebo "je nadmnozinou". Svoju odpoved dokazte.
a) h-1(L1 ^ L2) ? h-1(L1) ^ h-1(L2)
b) h-1(L1 U L2) ? h-1(L1) U h-1(L2)
(znak "^", resp. "U" znamena prienik, resp. zjednotenie)
Uloha 5
Hovorime, ze jazyk L' je odmocninou jazyka L,
(znacime L' = Sqrt(L))
ak plati
L' = { w | ww je slovo z jazyka L }
Najdite jazyk (nie nutne ten isty pre obe podulohy), pre ktory plati
a) (Sqrt(L))2 != L
b) Sqrt(L2) != L
("!=" znamena nerovna sa.)
Uloha 6
Nech u = abeceda, v = bababbab.
Kolko existuje homomorfizmov
z {a, b, c, d, e}* do
{a, b}*
zobrazujucich slovo u na slovo v?
Uloha 7
Nech L je jazyk a h je homomorfizmus.
Musia vzdy platit nasledovne tvrdenia?
a) h-1(h(L)) = L
b) h(h-1(L)) = L
Uloha 8
Nech L1 a L2 su jazyky.
Musia vzdy platit nasledovne tvrdenia?
a) (L1 ^ L2)* = L1* ^ L2*
a) (L1 U L2)* = L1* U L2*
(znak "^", resp. "U" znamena prienik, resp. zjednotenie)