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

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?

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.