# If $M$ recognizes an infinite language, then $M$ has a cycle [closed]

An NFA $M$ contains a cycle if there is a state $q$ and a string $x$ such that if $M$ is in state $q$ and reads string $x$, $M$ can return to state $q$. Prove:

If $M$ recognizes an infinite language, then $M$ has a cycle.

• This is a problem statement, not a question. Please include your own effort and a specific question reagarding it.
– Raphael
Sep 23, 2013 at 7:29

Whithout a cycle, each string can only traverse a state once. If it is at a state $q$, there exists no string $x$ that can return the machine to state $q$. So if a string can only traverse each state once, then we can bound the lenght of the string to k, the number of states. Thus you can only represent a finite number of strings if they are bounded in length ($\sum_{n=0}^{k-1} |\Sigma|^n$). Thus to recognize an infinite language, there must be a cycle.