IB102 — úkol 5 — řešení
Odevzdání: 25.10. 2010
Vypracoval: James Bond UCO: 007
Skupina: MI6
1. [2 body] Najdete jazyky L1, L2, L3 a L4 takove, aby byly splněny následující podmínky:
(a) Jazyky L1, L2 jsou ruzne a platí ~Ll = ~La.
(b) Jazyky L3, L4 jsou ruzne, platí ~Lg = ~L4 a zároven existuje relace ~ splňující podmínky Nerodovy vety pro oba tyto jazyky.
(Tj. ~ musé být relace pravé kongruence s konečným indexem taková, že L3 je sjednocením některých tréd rozkladu podle ~ a zéroven L4 je sjednocením některých tréd rozkladu podle ~.)
Sve resení zduvodnete, tj. zejmena popište všechny zmínene relace, napr. tak, ze popísete jejich trídy rozkladu.
Řešené mnůze vypadat napríklad takto:
(a) L1 = 0, L2 = E*. Pak zrejme ~Ll = ~La = E* x E*.
Poznamka: Podobne jsme mohli zvolit libovolní jiny jazyk spolu s jeho komplementem. Platí totiz, ze ~L = ~co-l. Mozních resení vsak existuje jeste víc, napríklad jazyky L1 = {w | |w| mod 3 = 0} a L2 = {w | |w| mod 3 = 2} sice mají neprázdní pninik, ale platí ~Li = ~La.
(b) L3 = E*, L4 = {e}. Pak ~Lg = E* x E*, ~L4 = {(e,e)}UE+ x E+. Formulovíno pomocí tríd rozkladu, ~Lg mí pouze jednu trídu obsahující vsechna slova a ~L4 mí dve trídy, jedna obsahuje pouze e, druhí vsechna ostatní slova. Dale vezmeme ~ = ~L4. To je zrejme prava kongruence s konecním indexem (2) a L3 i L4 jsou sjednocením nekterych tríd rozkladu podle ~.
IB102 — úkol 5 — řešení
Odevzdání: 25.10. 2010
Vypracoval: James Bond UCO: 007
Skupina: MI6
2. [2 body] Mejme následující jazyk:
L = {w G {0,1}* | w je binární zapis Čísla k takoveho, Ze k mod 3 = 1}
priCemZ za binarní zapis Čísla povazujeme pouze takovy zápis, ktery neobsahuje zbytečne levostranne nuly, tj. 0110 pro nas není binarní zapis čísla, zatímco 110 je.
(a) Určete index ~L a popiste trídy rozkladu podle ~L.
(b) Popiste relaci prave kongruence ~ s konečnám indexem takovou, ze ~ = ~L a pritom L je sjednocením nekterách tríd rozkladu podle ~.
Řešeni:
(a) Trídy rozkladu podle ~L jsou nasledující:
1. W
2. {0}-{0,1}*
3. {w G {1} • {0,1}* | w je binárním zapisem císla k takoveho, ze k mod 3 = 0}
4. {w G {1} • {0,1}* | w je binarním zápisem císla k takoveho, ze k mod 3=1}
5. {w G {1} • {0,1}* | w je binárním zápisem císla k takoveho, ze k mod 3 = 2}
Index ~L je tedy 5.
(b) Necht' ~ je relace ekvivalence urcena následujícími trídami rozkladu:
1. W
2. {0}
3. {0}-{0,1}+
4. {w G {1} • {0,1}* | w je binárním zápisem císla k takoveho, ze k mod 3 = 0}
5. {w G {1} • {0,1}* | w je binárním zápisem císla k takoveho, ze k mod 3=1}
6. {w G {1} • {0,1}* | w je binárním zápisem císla k takoveho, ze k mod 3 = 2}
Zrejme platí, ze ~ je relací prave kongruence s konecním indexem a ~ = ~L. L se rovná tríde rozkladu oznacene císlem 5.