IB102 - úkol 5
Odevzdání: 25.10. 2010
Vypracoval(a): UCO: Skupina:
1. [2 body] Najdete jazyky L1, L2, L3 a L4 takové, aby byly splněny nasledujúci podmínky:
(a) Jazyky L1, L2 jsou různě a platí ~Ll = ~La.
(b) Jazyky L3, L4 jsou různě, platí ~Lg = ~L4 a zaroven 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 rešení zduvodnete, tj. zejmena popište všechny zmínene relace, napr. tak, ze popísete jejich trídy rozkladu.
IB102 - úkol 5
Odevzdání: 25.10. 2010
Vypracoval(a): UCO: Skupina:
2. [2 body] Mejme následující jazyk:
L = {w E {0,1}* | w je binární zapis Čísla k takového, 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í zápis čí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 ~.