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
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.