Can a non deterministic finite automaton go into infinite loop?

Question

Here is the exact same question but on deterministic finite automaton. The case for deterministic finite automaton is simple. For each state only one transition is possible for each input symbol and quite intuitively one can verify that a DFA shall halt when the input string is exhausted.

Lately I came across a question as :

State true/false:

"Whether a finite state automaton halts on all inputs" is a decidable problem.

I came to the conclusion that the above statement is True, with the following thought process. Be it an $\epsilon$-NFA or DFA, every finite automata has an equivalent simplified DFA and hence it is this DFA which is bound to halt on all (finite) input.

Just as I mentioned above about $\epsilon$-NFA, I was wondering, that we can have an infinite loop in this finite automaton. Possibly using $\epsilon$ transitions as follows:

But the possible loop in the red path in the diagram is harmless (unlike a loop in Turing Machine TM), as it is just a parallel path, which me might not even consider while the parallel processing of the contemporary instances of NFA is going on.

I cannot possibly think of a situation of finite automata where it goes into a situation like TM. Is such a situation at all possible ?

Answer 1

Not really, unless you include TMs in some way or another in the "situation".

Any infinite loop in an NFA must constitute only of $\epsilon$ transitions (since the input is finite, if the loop would have "eaten up" some letters, it must also be finite). As you already know, its pretty easy to get rid of those epsilon transitions, so after we do it, the automaton will never have any other infinite loops.

I will highly recommend reading this for a few minutes, and try to understand the basic decidability properties of regular languages. In particular, we can decide whether two automatons accept the same language - which is something that is impossible when dealing with TMs instead.

Now lets talk about the question you saw - there isn't a good definition of "halting" for automatons, since they don't operate like TMs. Automatons accept a word only if there is a "good path" in the automaton's states for that word. Therefore, I think the question actually meant the following instead:

Given an NFA, we can think of emulating it by running it in a step-by-step basis. Considering that, is it decidable to know whether on all inputs, the emulation of this particular NFA (and not an equivalent DFA) will always either accept, or will never have 0 "running threads" in the emulation?

Notice that this question, now talks about whether a turing machine (that emulates the NFA behavior) halts or not. This question is well defined, and it is not as trivial to solve it anymore (since you must use this NFA and not any other NFA\DFA).