Let $\Sigma$ be the alphabet $\{a, b, c, d\}$ and let $R$ be the following relation on $\Sigma^*$: $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 example, $R(abba, babbb)$ is true and $R(abcb, cbbcb)$ is false.) How many (non-empty) sets are in the partition of $\Sigma^*$ corresponding to $R$? (That is, how many equivalence classes does R have?)

Any help will help.


migrated from stackoverflow.com Oct 21 '13 at 11:12

This question came from our site for professional and enthusiast programmers.

  • $\begingroup$ Could the close-voters leave a comment for their close-votes? The question might be poorly stated, but it is quite clear (and easy to solve): the PO is asking for the number of equivalence classes of the relation on $\Sigma^*$ defined as follows: two words are equivalent iff every letter occurring in one of the two words also occurs in the other one. $\endgroup$ – J.-E. Pin Oct 26 '13 at 15:15

If you look at two strings in your example $abba$ and $babbb$, they are composed of exactly the symbols from the set $\{a,b\}$, where each symbol appears at least once. So you can reduce the counting problem in your question to counting the number of subsets of $\{a,b,c,d\}$. Note that one equivalence class would be $\{\lambda\}$ where $\lambda$ denotes the empty string. How many subsets does $\{a,b,c,d\}$ have?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy