State complexity of converting epsilon-NFAs to NFAs without epsilon transitions

Question

I am well-aware of the result showing that one can convert an epsilon-NFA (that is, an NFA with epsilon transitions) $A$ to an NFA without epsilon transitions $A'$, where $L(A) = L(A')$.

Is there a similar result comparing the state complexities of $A$ and $A'$? That is, if one has an epsilon-NFA $A$ with $n$ states, is it true that there exists an equivalent NFA without epsilon transitions $A'$ that also has $n$ states?

Answer 1

Yes, we can transform an epsilon NFA into a NFA by keeping the same state set, basically adding new edges. If there is an $\varepsilon$ path from state $p$ to state $q$, and an edge from state $q$ to state $r$, then add an $a$ edge from $p$ to $r$. Also, if from state $p$ we can reach a final state then state $p$ can be made accepting. After these two steps we can remove the original $\varepsilon$ edges without changing the language.