# Prove: If finite automata M with k states accepts a string with at least k characters, then the language L(M) is infinite

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?

• You start with the definitions of everything and what requirements fall through from one Y to it's equivalent X. – ratchet freak Sep 9 '19 at 14:55
• Are you familiar with the pumping lemma? – Yuval Filmus Sep 9 '19 at 14:57
• Try drawing a FA with, say, four states. What happens when you give it an input of four characters? Hint: repeat. – Rick Decker Sep 9 '19 at 15:18
• I am aware of pumping lemma, however I am still trying to wrap my head around it. – Torppo Sep 9 '19 at 15:19
• The proof is exactly the same as the pumping lemma's. – Yuval Filmus 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.