What does it mean when the transition function of a NFA returns an empty set?

Question

Given a NFA, $N = (Q, \Sigma, q_0, \partial, F_Q)$, where $\partial$ is the transition function $Q \times (\Sigma \cup \{ \varepsilon \} ) \to \mathcal{P}(Q) $. So $\partial(q, a)$ returns a set, which can be any element of $\mathcal{P}(Q)$.

Sounds great, but I don't know how to interpret what's going on when the return value of the transition function is an empty set $\emptyset$. Say the machine is at the state $q$, and I apply the transition $\partial(q, a) = \emptyset$, will it end up in nowhere? Is it the same as saying the machine "halt"? So the input string is rejected and all the following symbols are discarded?

I interpret it like this: $\partial(q, a) = \emptyset$ means that the pair $(q, a)$ has a special transition that does nothing. Is this correct?

---

Background: I'm reading the online book here. In the book, they define/require the transition function of a DFA to be a total function $Q\times\Sigma \to Q$, so I never think about this "end up in nowhere" problem before.

---

In this section, I will provide an example to show what confuses me.

Given a NFA, $N=(Q,\Sigma, q_0, \partial, F)$, where $Q=\{q_0, q_1, q_2\}$, $\Sigma = \{a, b\}$, and $F=\{q_1\}$, and the transition function is defined as follow:

\begin{align} \partial (q_0, a) &= \{q_1\} \\ \partial (q_0, b) &= \{q_2\} \\ \partial (q_1, a) &= \{q_0\} \\ \partial (q_1, b) &= \emptyset \\ \partial (q_2, a) &= \emptyset \\ \partial (q_2, b) &= \{q_0\} \\ \end{align}

and there is no $\varepsilon$-transition on all states in $Q$.

Given the starting state is $q_0$ and the input string is $ab$, then:

1. It could get rejected. The fact that $\partial(q_1, b)=\emptyset$ doesn't make me confident that $b$ would be consumed.
2. It could get accepted. Because in the end, the machine needs to read/consume the input symbol regardless of the image of $\partial(q_1, b)$. If $\partial(q_1, b)=\emptyset$ would indeed consume the symbol $b$ without making any move, it would stay in the state $q_1$. If $q_1$ is a final state, it will get accepted.

Answer 1

If you have $\partial(q,a)=\emptyset$, that means that there is no transition out of $q$ that consumes symbol $a$. Therefore, if you are imagining an execution that is at state $q$ and is trying to consume symbol $a$, execution cannot continue [1]. We might informally say that it "gets stuck". (It is a little bit analogous to a process that core-dumps and crashes.)

Recall that a NFA accepts iff there is any execution run that consumes the entire input and ends in acceptance. Therefore, an execution run that gets stuck partway through cannot possibly count as an accepting trace.

It might be tempting to think that the execution run gets "stuck at $q$" or "remains at $q$". This isn't correct. The execution run doesn't continue; instead, it disappears from existence. A better intuition would be that the execution run dies / does not continue. It's not in any state at all any longer.

All of these are analogies and intuition to help you understand the math. The actual truth is given by the mathematical definition. In any case of any doubt or ambiguity, refer to the mathematical definition for the precise answer.

[1] Unless there is an epsilon-transition that lets execution make progress to another state that can read symbol $a$.

Answer 2

One key difference between a NFA and a DFA is the form of the transition function $\partial$.

In the case of a DFA, $\partial \colon Q \times \Sigma \to Q$ is a single-valued function, which means that, given the current state $q \in Q$ and after reading any symbol $\sigma \in \Sigma$, the DFA will always enter a single, well-defined state $q' \in Q$ (hence the name "deterministic").

In the case of a NFA, instead, $\partial \colon Q \times (\Sigma \cup \{\varepsilon\}) \to \mathcal{P}(Q)$ can be seen as a multi-valued function, which means that, given the current state $q \in Q$ and after reading any symbol $σ \in \Sigma$ or no symbol (this is why the singleton $\{\varepsilon\}$ is added in the second component of the domain of $\partial$), the NFA may enter any state $q'$ from a single, well-defined subset $Q' \subseteq Q$ of the set of states (hence the name "nondeterministic").

Since the set $Q$ of states of an NFA is finite, every $Q' \subseteq Q$ is also finite, in particular it can be empty.

If for a given state $q \in Q$ and symbol $\sigma \in \Sigma \cup \{\varepsilon\}$ (possibly no symbol) the image $\partial (q, \sigma)$ is empty, it simply means that there is no transition to a new state from the state $q$ after reading the input symbol $\sigma$ (possibly after reading no symbol). In this case, you cannot conclude immediately that the NFA must reject the input word. It just means that this particular nondeterministic transition path (that is, a sequence of transitions obtained by nondeterministically choosing a particular state from the image of $\partial$ as the starting point of the next transition) ends in the state $q$ when the input symbol to read (possibly none) is $\sigma$.

Thus, consider an NFA running for some input word following a particular transition path. Suppose that the NFA is in the state $q$ and is reading the symbol $\sigma \in \Sigma$ from the input word, and that $\partial(q, \sigma) = \emptyset = \partial(q,\varepsilon) $: then, that particular transition path is stuck (it cannot evolve more), and

1. if $q$ is an accepting state and $\sigma$ is the last symbol of the input word, then the NFA accepts the input word;

2. otherwise (that is, if $q$ is not an accepting state or $\sigma$ is not the last symbol of the input word), you have to look for some alternative transition paths that would circumvent this situation.

If no such an alternative transition path exists, then the NFA rejects the input word. For a formal account, see here.

---

In the example of NFA at the end of the OP, there is only one possible transition path starting in the state $q_0$ with the input word $ab$: such a transition path ends in the state $q_1$ after reading the first symbol $a$ and then it gets stuck. We are in situation 2. described above, because $a$ is not the last symbol in the input word $ab$ (the last symbol, i.e. $b$, has to be read, but no transition from $(q_1, b)$ is possible), even though $q_1$ is an accepting state. Since there are no alternative transition paths, the word $ab$ is rejected by that NFA.