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

   

Transcribed Image Text:

2. Let L be the set of all finite strings over A = {a,b} and let R be the following binary relation on L (num(a, x) denotes the number of occurrences of a in the string x): xRy 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? Explain why. (b) What is the number of equivalence classes of R which contain strings of length k? Explain why. (c) Are there any equivalence classes which contain just one string? If the answer is YES, give the number of such classes and provide some examples; if it is NO, explain why all equivalence classes contain more than one string. 2. Let L be the set of all finite strings over A = {a,b} and let R be the following binary relation on L (num(a, x) denotes the number of occurrences of a in the string x): xRy 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? Explain why. (b) What is the number of equivalence classes of R which contain strings of length k? Explain why. (c) Are there any equivalence classes which contain just one string? If the answer is YES, give the number of such classes and provide some examples; if it is NO, explain why all equivalence classes contain more than one string.

Answer rating: 100% (QA)

1 Sure I can help you with this problem a What is the number of strings in the equivalence class which contains ababa Explain why The number of string... View the full answer