0
$\begingroup$

I'm finding it difficult to understand why due to the pigeonhole principle, 2 distinct words must go to the same state in a DFA.

Is it that if there are n words and m states, where there are more words than states (n > m), that 2 words must end up in the same state?

Is this somewhere along the right path?

$\endgroup$

1 Answer 1

0
$\begingroup$

Count the number of strings reaching each state. If you have m states, and none is reached by two or more strings, then the total number of strings is at most m. If the number of strings is greater than m then one state is reached in two or more ways.

You can use the same argument if no state is reached by more than 100 strings, then the total number of strings is at most 100m. If you have more than 100m strings then one state can be reached by more than 100 strings.

$\endgroup$
1
  • $\begingroup$ "If you have more than 100m strings then one state can be reached by more than 100 strings." ─ here "can" should read "must". $\endgroup$
    – kaya3
    Aug 13, 2023 at 14:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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