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!

  • $\begingroup$ Construct a minimal DFA for your language. The equivalence classes are the languages of the states. $\endgroup$ – Yuval Filmus Feb 22 at 3:33
  • 1
    $\begingroup$ Hint: $A$ consists of words whose initial and final letters coincide (plus $\epsilon$). $\endgroup$ – Yuval Filmus Feb 22 at 5:00

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.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.