2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ You start with the definitions of everything and what requirements fall through from one Y to it's equivalent X. $\endgroup$ – ratchet freak Sep 9 at 14:55
  • $\begingroup$ Are you familiar with the pumping lemma? $\endgroup$ – Yuval Filmus Sep 9 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$ – Rick Decker Sep 9 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 at 15:19
  • $\begingroup$ The proof is exactly the same as the pumping lemma's. $\endgroup$ – Yuval Filmus Sep 9 at 20:45
2
$\begingroup$

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.

$\endgroup$

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.