In the formal solution it is written that in order to test whether or not two words u,v are equivalent, it's enough to check that uw in L iff vw in L for all w with |w|<=m.

However, I could not prove it, but only a weaker version of it - that it's enough to test for |w|<m^2.

If it's possible, I would like to see a proof that |w|<=m is enough.

Think of a w with length greater than m. It leads u and v to some state, right?

Now, we can see from the proof of the pumping lemma that there always exists a shorter string w' that does the same thing,

by "short-cutting" cycles.

Do you see it? Try and make it formal.

Thanks for the reply.

I still don't see it. After some w with |w|>m, both u and v are in some states [uw] and [vw]. Of course both u and v have gone through some cycles, but in principle they may be different cycles, so if I shortcut a cycle I might change the final state of the other path. I don't see what promises me that there is a cycle which *both* of them traversed, so that I can shortcut it, unless |w|>=m^2.

You are right Dean, this approach leads to m^2, and one needs to be a bit more subtle to prove that this also holds for m.

In fact, by carefully observing the algorithm for distinguishing equivalence classes (Lecture 3, p. 38), you can check that we succeed in

finding them (and thus the minimal automata) by only using "short" prefixes. You can also look for the "table-filling" algorithm

which lays it out more explicitly. Roughly, had you needed w of length more than m, the relation ~ would have had more than m equivalence classes.

Anyhow, giving a m^2 solution is perfectly OK for the purposes of the question, and will not be "harmed".

Thank you! Now it's clear