# How to use the Pigeonhole Principle to prove a DFA has a minimum number of states?

$$A = \{w \in \{a, b\}^* |$$ 10th character from the end of $$w$$ is $$b\}$$

Prove if DFA $$M$$ has $$L(M) = A$$ then $$M$$ has at least 1024 states.

So there's only 2 characters possible at any state, aside from the 10th character, which has to be $$b$$. Any character after that can be a or b, since we know the 10th character from the end is $$b$$.

I was told that the Pigeonhole Principle would be used to prove this, as well as contradicting or using the contrapositive was the way to go.

My answer was that if we took a string $$w$$ with a length of less than the number of states, say 9, then the principle says that a state will have to be repeated. So a string of 10 $$b$$'s in a row won't reach an accepting state because the path will waste a transition to loop or repeat a state that has been traveled to. Because a string failed when it shouldn't have, that contradicts the language?

I also have a few other reasonings that may work with the Pigeonhole Principle, but I am just wondering if my reasoning makes sense.

• @Evil We have not gone over Myhill-Nerode or minimizing. We have done NFA to DFA. I don't think it's necessary to actually create a DFA, just logically show that there should be 1024 or more states. Oct 22, 2016 at 3:03
• @Mikael for accepting a string with the DFA you have to remember the 10 initial symbols of the string and each symbol can have 2 possible values which gives the required number of states , although i am not sure how the pigenhole principle applies here. Oct 22, 2016 at 4:39
• Seems like a 10 character production is valid, and you can produce at most 1*2^9 states in 10 characters, so how can you prove this?
– par
Oct 22, 2016 at 7:26
• I don't understand your reasoning at all. I'm sure it doesn't constitute a valid proof. (You can't make assumptions on how the automaton works.)
– Raphael
Oct 22, 2016 at 8:08
• Who told you that the pigeonhole principle can be applied here? Even if it somehow can, a proof by contradiction is much more immediate. Hint: the automaton needs to count to 10 but it does not know when to start.
– Raphael
Oct 22, 2016 at 8:11