# Non equivalent states shortest word [closed]

My textbook contains a theorem that if you have a DFA and two states that are not-equivalent, then there is a differentiating word that has length smaller than amount of states in that DFA.

How do we prove this is true?

Use the pigeonhole principle. Let $w$ be the shortest differentiating word. Suppose its length is larger than the number of states of the DFA. Consider the sequence of states traversed on input $w$. What can you say about them? (Use the pigeonhole principle.)