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:
- It could get rejected. The fact that $\partial(q_1, b)=\emptyset$ doesn't make me confident that $b$ would be consumed.
- 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.
Best Answer
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$.