Can an NFA Reach Two Final States at the Same Time?

Yes. An NFA can have more than one accepting state reachable after the same input has been read. This happens when different computation paths branch and end in different accepting states.

The phrase “at the same time” needs a small qualification: one individual computation path is in one state at a time. But when you simulate an NFA, you can track the set of states reached by all possible paths. That set can contain several states, including several accepting states.

What an NFA does

A nondeterministic finite automaton (NFA) has a finite set of states, an input alphabet, a start state, a set of accepting states, and transitions that may lead to more than one state. Formally, a transition function is often written as

$$\delta: Q \times \Sigma \to \mathcal{P}(Q),$$

where $Q$ is the state set, $\Sigma$ is the input alphabet, and $\mathcal{P}(Q)$ is the set of all subsets of $Q$. Thus, from one state on one input symbol, an NFA may have no next state, one next state, or several next states.

The automaton’s possible computations branch whenever there is more than one next state. The NFA accepts a string if at least one of those computations consumes the entire string and ends in an accepting state. Other branches may end in non-accepting states or get stuck; that does not prevent acceptance.

A simple example

Consider an NFA with start state $q_0$, accepting states $q_1$ and $q_2$, and transitions

$$\delta(q_0,a)=\{q_1,q_2\}.$$

There are no other transitions. On input a, the automaton has two possible computations:

• $q_0 \to q_1$
• $q_0 \to q_2$

Both computations consume the whole input, and both end in accepting states. So after reading a, the reachable-state set is $\{q_1,q_2\}$, and the string is accepted. In the set-based simulation, both final states are present at the same input position.

The paths are alternatives, not one path that simultaneously occupies two locations. The set $\{q_1,q_2\}$ summarizes those alternatives.

How to check an input systematically

To simulate an NFA, keep a set of currently reachable states:

1. Start with the set containing only the start state. (For an NFA with epsilon transitions, first include every state reachable through zero or more epsilon transitions.)
2. For the next input symbol, take the union of all transitions on that symbol from states in the current set.
3. Repeat until the input is exhausted. With epsilon transitions, also include states reachable by epsilon transitions after each move.
4. Check whether the resulting set contains at least one accepting state.

For example, if the current set is $\{p,r\}$ and the next symbol is b, and

$$\delta(p,b)=\{u,v\}, \qquad \delta(r,b)=\{v,w\},$$

then the next set is the union $\{u,v\} \cup \{v,w\}=\{u,v,w\}$. If both $u$ and $w$ are accepting, the NFA has two accepting states reachable at that point. It accepts the input if that point is the end of the input.

What “final” means here

A final state is also called an accepting state. It does not mean that the automaton must stop as soon as it reaches that state. If input symbols remain, a computation may continue along available transitions. Acceptance is determined after the entire input has been consumed: a path must end in an accepting state then.

Therefore, reaching an accepting state partway through a string is not by itself enough. For instance, a path that reaches a final state after reading the first symbol but has no transition for the next symbol cannot accept the longer string on that path.

Common mistakes

• Assuming there can be only one accepting state. An NFA may have any number of accepting states, including none or all of its states.
• Requiring every branch to accept. NFA acceptance is existential: one complete accepting path is enough. Requiring every path to accept would be a different condition.
• Treating the reachable-state set as one computation. It is a compact way to record many possible computations, not a single physical run in several states.
• Checking for a final state before the input ends. A path must consume all input symbols and then finish in an accepting state.

A deterministic finite automaton (DFA), by contrast, has exactly one next state for each state-symbol pair, so a single input determines one state at each step. The subset construction converts an NFA into an equivalent DFA by treating each set of NFA states as one DFA state. This is why it is natural to describe an NFA simulation as tracking several states together, even though each individual path follows one state at a time.