# Do NFAs with $\varepsilon$-moves never terminate?

Suppose in an NFA we have an $\varepsilon$-move from a state $q_0$ to $q_1$. According to Sipser,

Without reading any input, the machine splits into multiple copies one following each of the exiting $\varepsilon$-arrows and one staying at the current state. Then the machine proceeds nondeterministically as before.

Here is an application of this logic to our case: upon reaching the state $q_0$ our machine splits into two copies: one in state $q_1$, one in state $q_0$. For the latter copy, execution continues as before, so again another copy of the machine is created in state $q_0$. Thus, a copy of the machine always in state $q_0$ will exist indefinitely.

Is this true? If no, why not? How should I then interpret the description given above?

• I don't find Sipser's explanation helpful. There is no splitting; there is not really a good "executionst" intuition for non-deterministic automata. Check the definition: it's about whether an accepting computation exists. – Raphael Apr 18 '18 at 5:08
• @Raphael Thanks for your comment! Would you mind offering a brief explanation why the splitting/forking interpretation/intuition is not a good one? – Andrey Portnoy Apr 18 '18 at 5:45

This is not true. The key to interpreting the quoted description correctly is noting that the splitting occurs without reading any input. So when we arrive at $q_0$, we split into two copies with the same input string left to be read, one in the state $q_0$, the other in the state $q_1$.
After the splitting, however, we have to continue reading the input string. So if $q_0$ does not have any other moves from it, the computation is simply stuck at $q_0$ and that branch of computation dies.