NFA-epsilon: epsilon loops, and how do I deal with them?

Question

I am currently studying Automatons and have one, albeit simple, question about NFA-epsilon 'loops'
I know that a string can advance using epsilon without having anything read. So my first question would be, if you had a chain of epsilon-arches, would you just jump to the end of the chain instantaneously (Figure 1) ?
My other question is; At the end (Figure 1) at the accept state there is en epsilon-arch going back to a previous state, would this cause a loop and in-turn cause the string to never halt, or would it just create another fork (endlessly?)?

My last question is, how would I approach said NFA-epsilon example with these example strings: 1011100, 0101111?
To me the second string would be accepted, while the first one would be rejected because it has 2 zeroes at the end of the string. I am unsure though!

(Figure 1)

Thanks in advance! :)

Answer 1

You would not "jump" to the end of the chain immediately. An epsilon transition is a convenience, a "way of modeling the systems whose current states are not precisely known". In fact, you would actually consider your self to be at all reachable (via epsilon transition) states at once. This is part of the non-determinism, you're not necessarily at one state, but rather can be at multiple at the same time.

In your example, starting at $q_0$, we have epsilon transitions allowing us to be in states: $\{q_0, q_1, q_2, q_4, q_5, q_6\}$ at the same time. This means all values that any of these states transition on, we can transition on. In your example, from $\{q_0, q_1, q_2, q_4, q_5, q_6\}$ we can transition on $\{1, 0\}$. In fact, because we're already at state $q_6$, we don't necessarily need to transition at all because we're already accepting.

For your second question, you would not be in an endless loop, similar to my previous explanation, having a loop of epsilon transitions would not affect how many states we're currently at. If we're at $q_5$, we're also at $q_6$, looping back to $q_5$ won't matter because we're already there. The importance of the loop is the fact that $q_5$ also transitions on $1$, so $q_6$ epsilon-transitioning to $q_5$ allows us to accept however many $1$'s we need.

---

I think an extremely helpful way to digest NFAs (because they can be confusing sometimes) is to apply the Powerset Construction or at least think about how it would be applied to your example. As fade2black said, the NFA will create many branches of computation, this construction will only create 1, which in my opinion makes it much easier to interpret.

In your example the powerset construction would look like this:

Set         \ Transition | 1                        | 0
-------------------------+--------------------------+-----
{q0, q1, q2, q4, q5, q6} | {q0, q1, q2, q4, q5, q6} | {q3}
{q3}                     | {q2, q4, q5, q6}         | N/A
{q2, q4, q5, q6}         | {q5, q6}                 | {q3}
{q5, q6}                 | {q5, q6}                 | N/A

We can then define:

$$\begin{align} A & = \{q_0, q_1, q_2, q_4, q_5, q_6\}\\ B & = \{q_3\}\\ C & = \{q_2, q_4, q_5, q_6\}\\ D & = \{q_5, q_6\}\\ \end{align}$$

And get the resulting equivalent DFA:

Then running your input becomes trivial.

Answer 2

if you had a chain of epsilon-arches, would you just jump to the end of the chain instantaneously

I am not sure for "instantaneously", but I would say it accepts the empty string $\epsilon$.

would this cause a loop and in-turn cause the string to never halt, or would it just create another fork (endlessly?)?

Your input string will be accepted. On any input, a NFA runs by creating many branches of computation in parallel and if one of them reaches the accept states, after it reads the last symbol of the input, then your string is accepted and the entire computation halts. You kind of choose at least onе fork that leads the NFA to the accept state.

how would I approach said NFA-epsilon example with these example strings: 1011100, 0101111?

Right the first string is not accepted, the second one is accepted.