IB102 — úkol 1 — řešení
Odevzdání: 27. 9. 2010
Vypracoval: James Bond UCO: 007
Skupina: MI6
1. [2 body] Mejme následující jazyky nad abecedou S = (a, b}.
Li = (a} • ((e} U (a}) L2 = (b} U (0 • (b}) L3 = (Li • L2) n L*
Zjistete, kolik slov obsahuje jazyk L3, a vypište je. Svou odpoved' zduvodnete.
Řešeni: Jazyk L3 obsahuje práve dve slova, jsou to slova a a aa. Zdůvodněni: Nejprve si prepíseme jazyky L1 a L2 do Citelnejsí podoby:
L1 = (a} • ((e} U (a}) = (a} • (e, a} = (a, aa} L2 = (b} U (0 • (b})     = (b} U 0      = (b}
Nyní je zrejme, ze jazyk L1 • L2 obsahuje prave vsechna slova, ktera zaCínají jedním nebo dvema symboly a, za nimiz nasleduje libovolní pocet symbolu b (vcetne nuloveho poctu), formalne tedy (a, aa} • (b}*. Jazyk Li pak obsahuje príve vsechna slova, kterí jsou tvorena pouze symboly a (vcetne prázdneho slova), formalne L* = (a}*. Jsou pouze dve slova, ktera patrí do obou techto jazyku, a to jsou prave a a aa. Proto platí:
L3 = (L • L*2) n L* = (a, aa}
IB102 — úkol 1 — řešení
Odevzdání: 27. 9. 2010
Vypracoval: James Bond UCO: 007
Skupina: MI6
2. [2 body] Necht' L je jazyk nad abecedou S = (a, b} tvořeny prave všemi slovy, která mají sudý poCet písmen a a zároveň sudá poCet písmen b. Zapište jazyk L pomocí jednoprvkových jazyku (a} a (b} s využitím operací sjednocení (U), zretezení (•), průniku (n) a iterace (*). Chcete-li pouzít jine operace nebo jazyky, musíte je nejprve definovat pomocí víse uvedenych operací a jazyku.
Bonusoví varianta za 4 body: Zapiste jazyk L bez pouzití operace pruniku.
Řešení: Pro zprehlednení zapisu si nejprve definujeme nísledující pomocne jazyky. Jazyk Li bude obsahovat vsechna slova se sudím poňtem a a jazyk L2 bude obsahovat vsechna slova se sudíym poňctem b.
Li = ((b}* • (a} • (b}* • (a})* • (b}* L2 = ((a}* • (b} • (a}* • (b})* • (a}*
Resení pak muzeme snadno zapsat takto: L = L1 n L2.
Řešení bonusove varianty: Nejprve si definujeme nasledující pomocne jazyky:
Li = ((a} • (a}) U ((b} • (b}) L2 = ((a} • (b}) U ((b} • (a})
Resení pak muzeme zapsat napríklad takto:
L = (Li U L2 • L* • L2)*
Vysvetlení: Slova, ktera mají sudí pocet a i b, musí bít nutne sude delky. Kazde takove slovo se tedy da rozdelit na posloupnost dvojic písmen. Tyto dvojice jsou dvou typu - bud' nemení paritu poňctu a a b (to jsou dvojice aa a bb), nebo mňení paritu poňctu a i paritu poňctu b (to jsou dvojice ab a ba). Dvojic prvního typu muze bít ve slove libovolní pocet, dvojic druheho typu musí bít nutne ve slove sudy pocet. (Paritou míníme sudost/lichost poctu písmen.)