Can a non-deterministic finite automaton die out before reading the entire string?

Question

I am new to automata theory and have a problem that I want to solve. We have to design an NFA that starts with "ab". I have the solution and it is given by:

However, my problem is: If the string does not start with $a$ then the machine will die out in such a case and will not read other letters in the given string, is this fine? I have read somewhere that the machine should not die out till the string is completely read (even if the string is not accepted), and such is not the case here.

Furthermore, if this is not the case then, why should the state $q_2$ needs to have an arrow over itself? Do I really need to care? Once the string is having an "$ab$" in the beginning, the machine knows it has to accept the input and can die out.

I am just confused, the given NFA confers that the machine can die out even without reading the whole string, Is this fine? And If it is and why to put a self-arrow over $q_2$?

Answer 1

Formally the transition function $\delta$ of a NFAs is a total function with domain $Q \times \Sigma$ and codomain $\mathcal{P}(Q)$, where $Q$ is the set of states and $\Sigma$ is your alphabet and $\mathcal{P}(Q)$ is the power set of $Q$.

The NFA accepts a string $s=s_1s_2s_3 \dots$ iff there is a sequence of states $q_0,q_1, \dots, q_n$ where $q_0$ is the initial state of the NFA and, for $i=1,\dots,n$, $q_i = \delta(q_{i-1}, s_i)$.

As a consequence, if there is no possible sequence of states that satisfies the above condition (what you seem to call "die out"), the NFA rejects.

A way to check whether an accepting sequence of states exists is that of keeping track of a set $S$ of states while simulating the NFA on the input string. Initially $S = \{q_0\}$, where $q_0$ is the initial state. Then, for each character $s_i$ of $s$, in order, update $S$ to $\bigcup_{q \in S} \delta(q, s_i)$. At the end of this process, accept if and only if $S$ contains a final state.

This shows that if $S$ becomes empty at any point during this process, then it will remain empty and the input string will be rejected.

Regarding your second question, 'Design an NFA that starts with "ab"', doesn't mean much. Maybe you wanted to design a NFA that recognizes all strings that start with "ab", i.e., those described by the regular expression $ab(a\mid b)^*$. If that's the case then if you were to remove the self-loop from $q_2$ you wouldn't be accepting all the needed strings. For example "abb" would be rejected.

Answer 2

Formally speaking, an NFA or DFA never “dies out”: for every state $q$ and for every character $a$ in the input alphabet, there is a state $q'$ such that there is a transition $q \xrightarrow{a} q'$. The state $q'$ is $\delta(q, a)$ where $\delta$ is the transition function in the definition of the automaton. The automaton only stops when it reaches the end of the input.

There is a very common convention when drawing automata to omit one hidden “dead” state $q_\dagger$ which is not accepting. Any missing transition in the drawing is a transition to $q_\dagger$, including transitions from $q_\dagger$ itself. If the automaton enters this state, it remains in this state. Nothing interesting happens once $q_\dagger$ is reached and we know that the input won't be accepted as soon as it's reached, so it's a dead state (More generally, any state from which it is impossible to reach an accepting state is called a dead state. Merging all the dead states into one doesn't change what language the automaton accepts, so it's common to speak of “the” dead state even though there could be many and some automata don't have one. If an automaton doesn't have a dead state, you can add one without changing the language; that state will be unreachable.)

So, for example, the automaton you drew has 4 states $\{q_0, q_1, q_2, q_\dagger\}$, and has 4 transitions that are not drawn: $q_0 \xrightarrow{b} q_\dagger$, $q_1 \xrightarrow{a} q_\dagger$, $q_\dagger \xrightarrow{b} q_\dagger$ and $q_\dagger \xrightarrow{a} q_\dagger$.

Hiding the implicit dead state simplifies the drawing. Making the dead state implicit, rather than defining the transition function as a partial function, simplifies reasoning about automata. It would be possible to define (non)deterministic finite automata with a partial transition function (DFAWAPTF/NFAWAPTF), and their theory would be basically identical to the theory of DFA/NFA, but reasoning would be more complicated since you'd have to have separate cases for $(q,a)$ pairs with a transition and $(q,a)$ pairs without a transition. Since every DFAWAPTF has a matching DFA and NFAWAPTF has a matching NFA, there is no point in reasoning about the WAPTF variants.

The state $q_2$ does need transitions to itself. If these transitions were not present, then an input such as $aba$ would lead to the sequence of transitions $q_0 \xrightarrow{a} q_1 \xrightarrow{b} q_2 \xrightarrow{a} q_\dagger$, so $aba$ would not be accepted. Without the transitions from $q_2$, the automaton would only accept the exact string $ab$, and not any other string starting with $ab$.