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

  • $\begingroup$ 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. $\endgroup$
    – Kevin Wu
    Jun 10 '17 at 8:28
  • $\begingroup$ @KevinWu, right, so applying the pigeonhole principle to pairs of states doesn't work. What else could you apply it to? $\endgroup$
    – D.W.
    Jun 10 '17 at 15:38

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