Počet bodov: 3
Kladný počet bodov dosiahlo: 5 ľudí (max. 10)
Cokolada uz bola ziskana :-)

Zadanie:
Predpokladajte, že R je ľubovoľný regulárny jazyk, S je ľubovoľný (nie nutne regulárny) jazyk.

Rozhodnite, ktoré z nasledovných jazykov sú regulárne a ktoré nie sú (resp. či musia alebo nemusia byť regulárne, v závislosti od R a S). Svoje rozhodnutie zakaždým čo najstručnejšie, ale dostatočne zdôvodnite. Pri zdôvodnení môžete bez dôkazu využívať uzáverové vlastnosti regulárnych jazykov, pumpovaciu lemu a skutočnosť, že nasledujúce jazyky nie sú regulárne: { aⁱ bⁱ | i>=0 }, { aⁱ b aⁱ | i>=0 }, { w | w patrí do {a,b}^* a #_a(w)=#_b(w) }, { w | w patrí do {a,b}^* a w=w^R }.

• L₁ = { aⁱx | |x|=i a x patrí do R }
• L₂ = { aⁱ | existuje x také, že |x|=i a x patrí do R }
• L₃ = { aⁱ | existuje x také, že |x|=i a aⁱx patrí do R }
• L₄ = { aⁿ² | n>=0 }
• L₅ = L₄^*
• L₆ = { aⁱ b^j | (i+j) mod 11 = 7 }
• L₇ = { ucv | u,v patria do {a,b}^* a #_a(u)=#_a(v) }
• L₈ = { aⁱwbⁱ | w patrí do {a,b}^* a i>=0 }
• L₉ = { uv | u,v patria do {a,b}^* a #_a(u)=#_b(v) }
• L₁₀ = množina slov v knihe Hopcroft, Ullmann: Formálne jazyky a automaty
• L₁₁ = { x | existuje y z R také, že xy patrí do S }
• L₁₂ = jazyk, ktorého všetky vlastné podmnožiny sú regulárne

Hodnotenie:
Počet bodov = 3 - počet nesprávnych odpovedí. (Nesprávna odpoveď je aj dobrá odpoveď + zlé/žiadne zdôvodnenie, dobrá odpoveď + nedostatočné zdôvodnenie = 0.5b) Uznáva sa prvých 10 riešiteľov s kladným počtom bodov. Každý študent môže túto úlohu odovzdať najviac dvakrát (t.j. jeden opravný pokus). Úlohu riešte samostatne! Kolektívne riešenia budú diskvalifikované ;-) V riešení pre každý jazyk najskôr VÝRAZNE napíšte svoju odpoveď, potom zdôvodnenie, uľahčíte a urýchlite mi tak opravovanie.

Bonus:
Prvý človek, ktorý bude mať 3 body a navyše správne odpovie o jazyku L₅' = L₄⁴ má u mňa čokoládu.

Spôsob odovzdania:
Riešenie úlohy odovzdávajte spísané v elektronickej podobe mailom na misof@ksp.sk, v subjecte uvedte FOJA premia 4. Akceptujú sa otvorené formáty, menovite .tex, .dvi, .ps, .pdf, (ak ináč nejde) .txt. (Používať M$ Word neodporúčame, ak sa však predsa len rozhodnete písať v ňom, môžete vytvoriť súbor .ps tak, že nainštalujete driver pre PostScriptovú tlačiaren a príslušný .doc dáte vytlačiť do súboru.)