# 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?

## 1 Answer

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.)

• well, it doesn't necessarily have to be the case that a pair of states is repeated, since one state could just loop to itself, except let's say the last letter in an input word w that is equal in length to the number of states. For the other state, we continuously transition to another state. In that case, no pair of states is repeated. Jun 10, 2017 at 8:28
• @KevinWu, right, so applying the pigeonhole principle to pairs of states doesn't work. What else could you apply it to?
– D.W.
Jun 10, 2017 at 15:38