0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is a problem statement, not a question. Please include your own effort and a specific question reagarding it. $\endgroup$ – Raphael Sep 23 '13 at 7:29
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.