2. Le t L be the set of all finite strings over A = {a, b} and let R be the foll

Question

2. Le t L be the set of all finite strings over A = {a, b} and let R be the following binary relation on L (num(a, z) denotes the number of occurrences of a in the string ): string x): zRy num(a, x) = num(a, y) ^ num (b, x) = num(b, y). Observe that R is an equivalence relation on L (a) What is the number of strings in the equivalence class which contains ababa? Explairn (b) What is the number of equivalence classes of R which contain strings of length k? Explain (c) Are there any equivalence classes which contain just one string? If the answer is YBS, why. why. give the number of such classes and provide some examples; if it is NO, explain why all equivalence classes contain more than one string.

Explanation / Answer

(a) Equivalance class is a set of objects in which all the elements are equivalent with respect to tha relation. now here the equivalance relation contains ababa i.e the equivalance class contains all the strings in which number of occurance of a is 3 and number of occurance of b is 2. so we will be done if u find the number of string in which there are 3 time occurance of a and 2time occurance of b. so the strings are {ababa,baaba,bbaaa,baaba,aabba,aaabb,aabba,abbaa,abaab,abaab}. hence there total 10 strings in the equivalance class.

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.