1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @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. $\endgroup$ – Mikael Oct 22 '16 at 3:03
  • $\begingroup$ @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. $\endgroup$ – Shubham Singh rawat Oct 22 '16 at 4:39
  • $\begingroup$ 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? $\endgroup$ – par Oct 22 '16 at 7:26
  • $\begingroup$ 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.) $\endgroup$ – Raphael Oct 22 '16 at 8:08
  • 1
    $\begingroup$ 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. $\endgroup$ – Raphael Oct 22 '16 at 8:11
1
$\begingroup$

http://www.owenstephens.co.uk/blog/2014/09/28/NFA_DFA.html

https://cseweb.ucsd.edu/~ccalabro/essays/fsa.pdf

Evil's link and this other link seem to show how to apply the Pigeonhole Principle to show how to answer my problem. The second one explains it more visually and in a more noob friendly fashion.

$\endgroup$
  • 2
    $\begingroup$ I am glad it was helpful. Maybe you could work out your example and make answer form it? $\endgroup$ – Evil Oct 24 '16 at 1:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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