3
$\begingroup$

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:

Diagram

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 ?

$\endgroup$
4
$\begingroup$

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).

$\endgroup$
1
  • 1
    $\begingroup$ Thanks for your answer. Indeed 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? is the solid and non ambiguous and also to the point "exact" sort of question. The meaning which you have put forward formally describes what probably the question setter might have in his mind. [The question was a GATE question of CS paper 1989] $\endgroup$ Sep 2 at 8:36

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.