I need to prove that if finite automata $M$ with $k$ states accepts a string with at least $k$ characters, then the language $L(M)$ is infinite. I have no idea where to start. Any suggestions?

  • $\begingroup$ You start with the definitions of everything and what requirements fall through from one Y to it's equivalent X. $\endgroup$ Sep 9 '19 at 14:55
  • 1
    $\begingroup$ Are you familiar with the pumping lemma? $\endgroup$ Sep 9 '19 at 14:57
  • $\begingroup$ Try drawing a FA with, say, four states. What happens when you give it an input of four characters? Hint: repeat. $\endgroup$ Sep 9 '19 at 15:18
  • $\begingroup$ I am aware of pumping lemma, however I am still trying to wrap my head around it. $\endgroup$
    – Torppo
    Sep 9 '19 at 15:19
  • $\begingroup$ The proof is exactly the same as the pumping lemma's. $\endgroup$ Sep 9 '19 at 20:45

Hint. Consider a word a length $\geqslant k$ accepted by $M$ and a successful path for this word. Now prove that this path goes at least twice through the same state, thus producing a loop.


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.