1
$\begingroup$

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?

Improve this question
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Raphael♦ Apr 18 '18 at 5:08
  • 1
    $\begingroup$ @Raphael Thanks for your comment! Would you mind offering a brief explanation why the splitting/forking interpretation/intuition is not a good one? $\endgroup$ – Andrey Portnoy Apr 18 '18 at 5:45
3
$\begingroup$

Sipser proposes an operational intuition for non-determinstic machines. As you have experienced, it's not very useful. In particular, it doesn't relate a lot to the formal definition, and there are more problems down the road¹.

I recommend sticking to the definition: an NFA accepts an input if there is a path from a starting to a final state labelled with the input. That really tells you all you need to know, and all there is to know.

Try to think mathematically instead of computationally.

  1. Parallelism and non-determinism are not the same; you can not build non-deterministic machines in a meaningful sense; cost models (e.g. in complexity theory) for non-deterministic machines don't make sense if you have the split/fork intuition; ...
Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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