-1
$\begingroup$

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?

$\endgroup$

closed as off-topic by David Eppstein, Kaveh, Emil Jeřábek supports Monica, Hsien-Chih Chang 張顯之, Jan Johannsen Jun 12 '17 at 7:31

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – David Eppstein, Kaveh, Emil Jeřábek supports Monica, Hsien-Chih Chang 張顯之, Jan Johannsen
If this question can be reworded to fit the rules in the help center, please edit the question.

1
$\begingroup$

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

$\endgroup$
  • $\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.