Can't understand what is expected of me in this equivalence relation problem.

35 Views Asked by At

I am having trouble understanding what is expected of me in this exercise. Should I check if there is reflexivity, transitivity and symmetry?

For each of the following partitions of the set{a,b}<=3, made with the words of the alphabet {a,b} where the length <4, describe the equivalence relation, that breeds it (made it):

  1. {{null element}{a,b}{aa,ab,ba,bb}{aaa,aab,aba,abb,baa,bab,bba,bbb}}

  2. {{null element,a,b}{aa,ba,aaa,aab,baa,bab}{ab,bb,aba,abb,bba,bbb}}

1

There are 1 best solutions below

2
On BEST ANSWER

It looks like in each part of the problem you've been given a partition of this set of words into some equivalence classes, and have been asked to describe what the equivalence relation is. Checking whether it's reflective, symmetric and transitive is pointless: that follows from the trivial same-equivalence-class description, but you need to give a different one. To wit:

1) Two words are equivalent iff of the same length.

2) Two words are equivalent iff they have the same second character (taken as null if the word's length is less than $2$).