I'm doing a problem where I need to find the equivalence classes of the language below:
Let A = {x ∈ {0, 1}* | #(01, x) = #(10, x)}, where, for a, b ∈ {0, 1}*, #(ab, x) is the number of places in x where an a is immediately followed by a b.
So I can start to see some equivalence classes. 1* and 0* both are in A, because they both have zero 10's and 01's, so the condition holds. I don't really know how I would describe the other equivalence classes?
Any help would be great!
It's a trick question.
They try to make you think that you have to count how many 01 strings and how many 10 strings there are, but you don't have to.
Say the first letter is 0. So far, no 01 and no 10 strings. This doesn't change if there are more zeroes. But if we find a 1, we now have got a 01 string. Nothing changes until we get a zero, and we have one 01 and one 10 strings. Again, more zeroes don't change this, the next 1 means the number of 01 strings is one higher than 10, and the next 0 after that makes the number equal again.
You can see that if we start with a 0 and process more letters, every time the string ends with a 1 the 01's are one ahead of the 10's, and when the string ends with a 0 their counts are equal.
You do the same for the case that the string starts with a 1. Again the counts are equal every time the last digit is a 1 and unequal every time the last digit is 0. Counts are equal every time the first and last digits are the same.
