IB102 - úkol 4, příklad 2
Odevzdání: 15.10. 2012
Vypracoval (a): Skupina:
UCO:
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ů Li,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 Li,L2 a prefixové ekvivalence ~Li,~l2)-
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 A L2 ^ L{). Rozhodněte a zdůvodněte i tento případ.