1 Replies - 1343 Views - Last Post: 30 September 2013 - 10:53 AM

#1 deprosun  Icon User is offline

  • D.I.C Regular

Reputation: 0
  • View blog
  • Posts: 292
  • Joined: 16-November 10

Equivalence classes

Posted 30 September 2013 - 10:38 AM

Let Σ be the alphabet {a, b, c, d} and let R be the following relation on Σ*: R(x, y) is true if every letter in string x also occurs in y, and every letter in string y also occurs in x. (For, R(abba, babbb) is true and R(abcb, cbbcb) is false.) How many (non-empty) sets are in the partition of Σ* corresponding to R? (That is, how many equivalence classes does R have?)

I think it would be 16, because:
it doesn't matter if there are any repeated letters. A string x has a relation to all other strings y that contain same letters, and the collection of the y's with that x is a set called equivalence class of x. Correct?

If so, if x = abba (which is basically consisted of a and b's), equivalence class of x with contain all y containing ab's. ab is one of the possible subsets. other are abcd, ad, ac, dc, dcb....etc. And there are 2^4 possible strings. So there are 2^4 equivalence classes.

Correct?

Is This A Good Question/Topic? 0
  • +

Replies To: Equivalence classes

#2 deprosun  Icon User is offline

  • D.I.C Regular

Reputation: 0
  • View blog
  • Posts: 292
  • Joined: 16-November 10

Re: Equivalence classes

Posted 30 September 2013 - 10:53 AM

or actually 15 because we need a non empty set.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1