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, 2019 at 14:55
  • 1
    $\begingroup$ Are you familiar with the pumping lemma? $\endgroup$ Sep 9, 2019 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, 2019 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, 2019 at 15:19
  • $\begingroup$ The proof is exactly the same as the pumping lemma's. $\endgroup$ Sep 9, 2019 at 20:45

1 Answer 1


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 and acknowledge you have read our privacy policy.

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