# 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)|$$

• What does “condition number” mean? What does “maturity of the algorithm” mean? These are bad translations, and I don't know what the right concept is. – Gilles 'SO- stop being evil' May 21 '12 at 23:36
• What have you tried? What techniques have did you learn in your lessons, that may be applicable here? Where are you stuck? – Gilles 'SO- stop being evil' May 21 '12 at 23:37
• condition->state; maturity->complexity (: looks like google-translate. – Ran G. May 22 '12 at 2:54
• Exercise 5.1, due May 24th. – Raphael May 30 '12 at 8:05

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).