IB102 - úkol 4, příklad 2 - řešení Odevzdání: 15.10. 2012
Vypracoval: James Bond UCO: 007
Skupina: MI6
1. [1 bod] Rozhodněte a zdůvodněte, zda platí toto tvrzení:
Existuje abeceda E a regulární jazyky L1? L2 nad E takové, že ~Li 7^ ~l2 a zároveň je pravá kongruence taková, že L2 je sjednocením některých tříd rozkladu E* podle ~Li-
(Pozn.: Pokud bude Vaše odpověď "ano, platí", uveďte zcela konkrétní příklad abecedy E, jazyků L±,L2 a prefixových ekvivalencí ~Li,~l2- Pokud bude Vaše odpověď "ne, neplatí", pokuste se zdůvodnit, proč to neplatí pro žádnou abecedu E, jazyky L±,L2 a prefixové ekvivalence ~Li,~l2)-
Řešení Tvrzení platí. Důkaz. Nechť
E = {a}, Li = {-u; J \w\ = 1 mod 4} , L2 = {-u; | \w\ = 1 mod 2}
pak
u ~Li v -é^U- \u\ mod 4 = \v\ mod 4 u ~l2 v <^=4> \u\ mod 2 = \v\ mod 2
Třídy rozkladu E* podle jsou:
Xq = {-u; | \w\ = 0 mod 4} Xi = \w | |w| = 1 mod 4} = Li X2 = {-u; | \w\ = 2 mod 4} X3 = {-u; | |w| = 3 mod 4}
Třídy rozkladu E* podle jsou:
Y0 = {w | H = 0 mod 2} = X0 U X2
1^ = [w j |w| = 1 mod 2} = Xx U X3 = L2
Tedy skutečně L2 je sjednocením některých (Xl,X3) tříd rozkladu E* podle ~Li- D
Bonus: [+1 bod] Uvažte zároveň, že platí následující dodatečná podmínka: jazyky L\ a L2 jsou nesrovnatelné (tedy L\ ^ L2 í\ L2 ^ L\). Rozhodněte a zdůvodněte i tento případ.
Řešení Tvrzení platí. (Nelze však použít jazyky z první části, protože tam L\ C L2)
Důkaz. Nechť
S = {a}, L\ = \w | \w\ = 1 mod 4} , L2 = {w | \w\ = 0 mod 2} Pak ~Li, ~l2 Jsou definované stejně jako v předchozím příkladě a platí:
X1 = L1
Y0 = X0 U X2 = L2
Tedy skutečně L2 je sjednocením některých (X0,X2) tříd rozkladu E* podle a zároveň Li ^ L2 AL2 % Lx. □