Getting an NFA with only one initial and final state without epsilon transitions

Question

Given an NFA with more than one initial or final state, it is possible to convert it to another NFA with only one initial or final state by using epsilon transitions. To remove the epsilon transitions, we may need to add final or initial states, depending on the method used (backwards removal vs forward removal).

Is there an efficient way to convert an NFA to an equivalent NFA with only one initial and final state, and no epsilon transitions? Converting it to a DFA can be exponential, so is there a better way to achieve this?

Answer 1

Yes, in fact we can. Provided the original automaton does not accept the empty string $\varepsilon$.

The construction is as follows. We start with the usual NFA with a single initial state (and no $\varepsilon$-edges). Add a new final state $f$. Whenever there is a transition $(s,a,t)$ into a final state $t$ we add a copy $(s,a,f)$ into new final $f$. Now demote every original final state into ordinary.

Voila, the new automaton accepts the original language except for $\varepsilon$, but has only a single final state.