The order of ε-transitions in NFA

Question

I'm reading 'Introduction to the Theory of Computation' by Michael Sipser. He gives an example of a NFA, stating that this particular automaton accepts $a$ (he lists other strings as well, I just want to focus on $a$).

But when he demonstrates how to convert the NFA to an equivalent DFA, he says: state $1$ goes to $\emptyset$ on $a$ because no $a$ arrows exit it. [...] Note that the procedure in Theorem 1.39 [on equivalence of DFAs and NFAs] specifies that we follow the $\epsilon$ arrows after each input is read.

So, if $\epsilon$-transitions happens only after some input (as the author defines), then in the initial state $1$, when $a$ is given, the NFA should 'die' as $\delta(1, a) = \emptyset$. The transition to state $3$ never happens, the NFA doesn't accept $a$. Doesn't the author contradicts himself?

I can think of couple possible explanations: 1) the very first transition of a NFA is $\delta(1, \epsilon)$ just by definition, 2) $a\epsilon=a$, so $\delta(1, a)$ = $\hat{\delta}(1, a\epsilon)$ = $\delta(1, \epsilon)\cup\delta(1, a)$, but then again the author said state $\{1\}$ goes to $\emptyset$ on $a$, not ${3}$

Answer 1

I think the answer is somewhat subtle and lies in Sipser's definition of what it means for an NFA to accept a string.

Let $N = (Q,\Sigma,\delta,q_0,F)$ be an NFA, and $w$ a string over the alphabet $\Sigma$. Then we say that $N$ accepts $w$ if we can write $w$ as $w=y_1y_2\dots y_m$, where each $y_i$ is a member of $\Sigma_\varepsilon$ and ...

Compare this with his definition of what it means for a DFA to accept a string:

Let $M = (Q,\Sigma,\delta,q_0,F)$ be a DFA and let $w=w_1w_2\dots w_n$ be a string where each $w_i$ is a member of the alphabet $\Sigma$. Then ...

Therefore, by his definitions, his NFA $N_4$ accepts $a$ as it can be written as $a=\varepsilon a$, and $\varepsilon$ and $a$ are both members of $\Sigma_\varepsilon$.

Answer 2

An NFA can always choose to take an $\varepsilon$-transition (if one exists) without reading any input, so your NFA would indeed accept the string $a$ by following the transitions $1 \xrightarrow{\varepsilon} 3 \xrightarrow{a} 1$ and ending up in an accepting state. This is because the NFA nondeterministically chose to follow the $\varepsilon$-transition before reading $a$ from the input.

However, when converting an NFA to a DFA we have to resolve the nondeterminism in some way. The procedure presented by Sipser in Theorem $1.39$ follows the convention that $\varepsilon$-transitions are followed after each input symbol is read, but, as he also states, a procedure based on following $\varepsilon$-transitions before each input symbol is read would work equally well. It is only a matter of the convention used to resolve the nondeterminism in the NFA.

If you look at Example $1.41$ and the DFA resulting from the conversion in Figure $1.43$, you will notice that the initial state is $\{1,3\}$ (the union of states $1$ and $3$ from the NFA) because the NFA have initial states $1$, but it can also go to $3$ with an $\varepsilon$-transition without reading any input. Therefore, the initial state in the DFA is the union of the two.