Vo všetkých úlohách predpokladajte (pokiaľ nie je uvedené ináč), že L, L₁, L₂ atď. sú ľubovoľné jazyky a h je ľubovoľný homomorfizmus. Zjednotenie značíme u, prienik ^, doplnok ^C.

Definície

• Mocnina jazyka: L⁰={epsilon}, L¹=L, Lⁿ⁺¹=L.Lⁿ
• Uzáver (Kleeneho *): L^* = zjednotenie Lⁱ cez všetky i>=0.
• Homomorfizmus (slov): Zobrazenie h zo Sigma₁^* do Sigma₂^*, pre ktoré platí, že pre ľub. slová u,v zo Sigma₁^* platí h(u.v)=h(u).h(v).
• Homomorfizmus (jazykov): Obraz jazyku L homomorfizmom h značíme h(L) a definujeme ho ako jazyk { h(w) | w patrí do L }.
• Inverzný homomorfizmus (slov): Zobrazenie h^-1 také, že h^-1(w)={ u | h(u)=w }
• Inverzný homomorfizmus (jazykov): Značíme h^-1(L) a definujeme ako zjednotenie h^-1(w) cez všetky w z L.

Úlohy

1. (o iterácii 1)
   • Rozhodnite, či platí: (L₁.L₂)^* = L₁^*.L₂^*
   • Existujú jazyky L₁, L₂ také, aby prienik jazykov L₁^* a L₂^* bol konečný a neprázdny?
2. (o iterácii 2) Rozhodnite, či platí:
   • Ak L=L^*, tak L=LL
   • Ak L=LL, tak L=L^*
   • Ak L²=L³, tak L=L²
3. (o homomorfizme)
   • Koľko existuje rôznych homomorfizmov (z {a,b,c,d,e}^* do {a,b}^*), ktoré zobrazia slovo abeceda na abbababb?
   • Koľko existuje rôznych homomorfizmov (z {a,b,c,d,e}^* do {a,b}^*), ktoré zobrazia slovo bedac na abbababb?
4. (o inverznosti h^-1) Rozhodnite, aký je vzťah medzi uvedenými množinami (sú rovnaké, jedna je podmnožina druhej, nič z predchádzajúceho):
   • h^-1(h(L)) a L
   • h(h^-1(L)) a L
5. (o vlastnostiach h) Rozhodnite, aký je vzťah medzi uvedenými množinami (sú rovnaké, jedna je podmnožina druhej, nič z predchádzajúceho):
   • h(L₁ ^ L₂) a h(L₁) ^ h(L₂)
   • h(L₁ u L₂) a h(L₁) u h(L₂)
6. (o vlastnostiach h^-1) Rozhodnite, aký je vzťah medzi uvedenými množinami (sú rovnaké, jedna je podmnožina druhej, nič z predchádzajúceho):
   • h^-1(L₁ ^ L₂) a h^-1(L₁) ^ h^-1(L₂)
   • h^-1(L₁ u L₂) a h^-1(L₁) u h^-1(L₂)
7. (o zelených jazykoch) Hovoríme, že jazyk L je zelený práve vtedy, ak platia nasledovné tvrdenia:
   • L je nad abecedou {a,b}
   • Ak slovo u patrí do L, tak aj každé slovo uv patrí do L (kde v je ľubovoľné slovo nad {a,b}^*)
   Dokážte, že zjednotenie aj prienik ľubovoľného (aj nekonečného!!) počtu zelených jazykov je zelený jazyk.