How do cycles of non-consuming transitions in NFAs influence their halting properties?

Question

I am in a class that is going over NFAs. The way they are described is a set of states, one of which is the start state, zero or more are accept states, and one or more transitions between them, which consume a symbol of the language or a lambda transition which does not consume a symbol from the string.

One thing that was mentioned is that languages defined by NFAs are regular, and thus can be parsed in constant time (since strings are finite). We then went through the basic pathfinding sort of algorithm where we try paths until we find one that consumes the entire string and if one path completely consumes the string and ends in an accept state - hurray.

Now, if there is a non-consuming transition from one state to itself, or another non-consuming loop in the NFA, that algorithm wouldn't halt.

Are those sorts of loops explicitly forbidden? Is halting not a required property of NFAs? Where is the disconnect in my understanding?

Answer 1

No, the $\lambda$-loops you talk about are not forbidden. But they do mean one has to be careful.

The actual way to determine if an NFA accepts its input is as follows. Note that this takes linear time in the length of the input, not constant time as you say in the question. First, for each state $q$ of the automaton, use a graph reachability algorithm to compute the set of states $\Lambda(q)$ that can be reached from $q$ using only $\lambda$-transitions. For a fixed automaton, with a fixed number of states and fixed transition function, this can be done in constant time. Note that $q\in\Lambda(q)$ for every $q$, since you can reach $q$ from itself by doing some number of $\lambda$-transitions: specifically, that number is zero. This means that $\lambda$-transitions from a state to itself are completely harmless.

To determine whether the automaton accepts its input, we just keep track of the set of states that the automaton "might" be in after reading each successive character of the input. Initially, it could be in any state in $\Lambda(q_0)$. If, after reading some characters, it could be in any state in $S\subseteq Q$ then, when it reads character $a$, it could be in any state in $\Lambda\Big(\bigcup_{s\in Q}\delta(s,a)\Big)$. It accepts if, at the end of the computation, the set of states it might be in includes at least one accepting state. Note that, at any time, the set of states the automaton could be in is bounded by the fixed constant $|Q|$ so all the manipulations needed on the set of possible states can be done in constant time per character the machine reads, independent of the length of the input.

Answer 2

1. The complexity for parsing a string is at least the length of the string( hence not constant).

2. The loops are not forbidden and halting is a required property. See this for the details of the definition of $NFA$.

3. It is possible to show that, any $NFA$ having $\lambda$-transitions can be converted to a $DFA$ (which by definition has no $\lambda$-transition) accepting the exact language as the $NFA$. Since $DFA$ always halts and the conversion of NFA to DFA can be done, it is safe to say that $NFA$ always halts.