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.

Improve this question
$\endgroup$
6
  • $\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, 2016 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, 2016 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, 2016 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, 2016 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, 2016 at 8:11

1 Answer 1

Reset to default
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.

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

Your Answer

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

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