Transforming an NFA into an NFA of similar size but without $\epsilon$-transitions

I'm learning for the exam and have problems with this task:


Describe an algorithm that transforms a given NFA $A = (Q, \Sigma, \delta, q_0, F)$ (which may have $\epsilon$-transitions) into an equivalent NFA without $\epsilon$-transitions with the same condition number. And then determine the maturity of the algorithm. The algorithm should have a running time $O(|Q| · |\delta|)$ where
$$|\delta| := \sum_{\substack{q\in Q\\ a\in\Sigma\cup\{\epsilon\}}} |\delta(q,a)|$$

The obvious answer is: the powerset construction gets rid of $\varepsilon$-transitions, so you can use it. It blows up the automaton exponentially in the worst case, though, so it is not directly applicable. However, you can use the part that deals with $\varepsilon$-transitions and keep nondeterminism.


That is, if a state $q$ has an $\varepsilon$-transition to $q'$, add all outgoing transitions of $q'$ to $q$ and remove the $\varepsilon$-transition.
You have to iterate this process for every state because there may be chains of $\varepsilon$-transitions. In the worst case, you reach all transitions (for every state), causing the required runtime bound (to be sharp).

Note that formally, this does not change the number of states. It might lead to isolated states, though, that can safely be dropped.

StackExchange Computer Science Q#1983, answer score: 2