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
$\begingroup$
$\endgroup$
2
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 WuJun 10, 2017 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, 2017 at 15:38