IB102 úkol 4, příklad 1 Odevzdání: 15. 10. 2018 Jméno: UČO: list učo body Oblast strojově snímaných informací. Své učo a číslo listu vyplňte zleva dle vzoru číslic. Jinak do této oblasti nezasahujte. 1. [2 body] Uvažte následující čtyři relace na slovech nad abecedou {a, b}: u R1 v ⇐⇒ u je prefixem v nebo v je prefixem u u R2 v ⇐⇒ u = v = ε ∨ první písmeno u je stejné jako první písmeno v ∧ poslední písmeno u je stejné jako poslední písmeno v u R3 v ⇐⇒ |u| < 2 ∧ |v| < 2 ∨ poslední dva znaky u jsou stejné jako poslední dva znaky v u R4 v ⇐⇒ #a(u) − #b(u) = #a(v) − #b(v) Pro každou z uvedených relací rozhodněte, zda se jedná o ekvivalenci. Pokud to není ekvivalence, dokažte proč. Pokud to ekvivalence je, rozhodněte, zda jde o pravou kongruenci. Pokud se o pravou kongruenci nejedná, dokažte proč, pokud ano, určete její index. Všechny kroky náležitě zdůvodněte. Zde uvádíme praktickou pomůcku pro lepší přehled: ekvivalence? pravá kongruence? důkaz index? důkaz ano ne ano ne • R1 Nejedná se o ekvivalenci, protože relace není tranzitivní. Protipříkladem mohou být prázdné slovo, které je prefixem kteréhokoliv slova, a dvě další slova, z nichž ani jedno není prefixem druhého. Například nechť u = a, v = ε a w = b. Platí, že v je prefixem u a zároveň v je prefixem w, ale ani jedno ze slov u a w není prefixem druhého z nich. Tedy (u, v) ∈ R1 ∧ (v, w) ∈ R1, ale (u, w) /∈ R1. • R2 Relace je ekvivalencí. Reflexivitu buď zajišťuje první podmínka u = v = ε nebo shodnost prvního a posledního písmene stejného slova. Symetrie a tranzitivita plyne z toho, že prázdné slovo je v relaci jen samo se sebou a pro neprázdná slova ze symetrie/tranzitivity rovnosti znaků. Také se jedná o pravou kongruenci. Pokud byla původní slova prázdná, přidáním stejného písmene na konec slova budou tato opět shodovat a splňovat druhou podmínku. Pokud slova byla v relaci, protože se shodovala v prvním a posledním znaku, nově přidané písmeno první znak neovlivní a přidaný poslední znak bude také stejný pro obě slova. Relace je tedy pravou kongruencí, jejíž index je 5 – do jedné třídy spadá prázdné slovo, do dalších všechna ostatní slova podle toho, na jaká písmena začínají a končí, jedná se tedy o třídy [ε]R2 , [aa]R2 , [ab]R2 , [ba]R2 , [bb]R2 . Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi. IB102 úkol 4, příklad 1 Odevzdání: 15. 10. 2018 Jméno: UČO: list učo body Oblast strojově snímaných informací. Své učo a číslo listu vyplňte zleva dle vzoru číslic. Jinak do této oblasti nezasahujte. • R3 Relace R3 je ekvivalencí, splňuje reflexivitu (srovnáváme délku slova či poslední dvě písmena se slovem samým), symetrii (konjunkce pro slova kratší než 2 je symetrická, nebo mají obě slova stejné dva poslední znaky) i tranzitivitu (podmínky disjunkce se vylučují a obě z podmínek fungují mezi více slovy tranzitivně). Nejedná se však o pravou kongruenci, jako protipříklad uvažme slova a a ε. Tato slova jsou v relaci R3, protože |a| < 2 a |ε| < 2, ale přidáme-li za obě slova a, výsledná slova aa a a v relaci R3 nebudou (|aa| 2, ani dvě poslední písmena těchto slov nejsou stejná). • R4 Relace R4 je ekvivalencí, splňuje reflexivitu (rozdíl počtu znaků a a b v témže slově je stejný), symetrii (ze symetrie =) i tranzitivitu (rozdíl počtu a a b musí být u všech tří slov stejný). Jedná se také o pravou kongruenci, neboť k oběma slovům přidáváme suffix se stejným počtem znaků b a a (tedy rozdíl se změní u obou slov stejně). Její index není konečný, třídy rozkladu budou odpovídat možným rozdílům počtu znaků a a b, kterých je nekonečně mnoho. Formálněji, uvažme slova tvaru wn = an, n ∈ N. Vezměme libovolná dvě slova ai, aj taková, že i = j. Připojíme-li ke každému z nich slovo ε, dostaneme opět ai, aj, platí, že (ai, aj) /∈ R4, tedy wi, wj patří do různých tříd rozkladu a tedy tříd rozkladu podle R4 je alespoň tolik, kolik přirozených čísel. Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.