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.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ This is a problem statement, not a question. Please include your own effort and a specific question reagarding it. $\endgroup$– Raphael ♦Sep 23, 2013 at 7:29
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.