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

CC BY-SA 3.0
2017-06-10T08:28:30.150Z
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.
Kevin Wu
CC BY-SA 3.0
2017-06-10T15:38:52.013Z
@KevinWu, right, so applying the pigeonhole principle to *pairs* of states doesn't work.  What else could you apply it to?
D.W.
CC BY-SA 3.0
2017-06-09T22:16:25.410Z
2017-06-09T22:16:25.410Z
D.W.
<p>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.</p>

<p>How do we prove this is true?</p>

<dfa>
Non equivalent states shortest word
Kevin Wu
# Non equivalent states shortest word

(Asked by: username_0 on 2017-06-09)

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?

**Tags:** dfa

---

## 1 answers

### Answer by username_1 on 2017-06-09. Score: 1

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

> **Comments:**
> **username_0**: 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.  
> **username_1**: @KevinWu, right, so applying the pigeonhole principle to *pairs* of states doesn't work.  What else could you apply it to?  

---

