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$
$\endgroup$
5
-
$\begingroup$ You start with the definitions of everything and what requirements fall through from one Y to it's equivalent X. $\endgroup$– ratchet freakCommented Sep 9, 2019 at 14:55
-
1$\begingroup$ Are you familiar with the pumping lemma? $\endgroup$– Yuval FilmusCommented 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$– Rick DeckerCommented 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$– TorppoCommented Sep 9, 2019 at 15:19
-
$\begingroup$ The proof is exactly the same as the pumping lemma's. $\endgroup$– Yuval FilmusCommented Sep 9, 2019 at 20:45
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
