Epsilon-moves can be eliminated from NFAs

Define an epsilon-free NFA $N^{\mathrm{\prime }}=(Q,\mathrm{\Sigma },{\delta }^{\mathrm{\prime }},q_0,F^{\mathrm{\prime }})$ by ${\delta }^{\mathrm{\prime }}(q,a):={\bigcup }_{r\in \mathrm{ECl}(q)}\mathrm{ECl}(\delta (r,a))$ for $q\in Q$ and $a\in \mathrm{\Sigma }$, and by $F^{\mathrm{\prime }}:=\{q\in Q:\mathrm{ECl}(q)\cap F\mathrm{\ne }\mathrm{\varnothing }\}\mathrm{.}$ Thus one $a$-move of $N^{\mathrm{\prime }}$ does exactly what $N$ can do by any number of $\epsilon$-moves, then one $a$-move, then any number of $\epsilon$-moves.

We claim that for every nonempty word $w$, the states reachable from $q_0$ in $N^{\mathrm{\prime }}$ after reading $w$ are exactly the states reachable from $q_0$ in $N$ after reading $w$. The proof is by induction on $\mathrm{\mid }w\mathrm{\mid }$: for one letter this is the definition of ${\delta }^{\mathrm{\prime }}$, and appending one more letter repeats the same closure-before-and-after simulation.

If $w=\epsilon$, then $N$ accepts $w$ exactly when $\mathrm{ECl}(q_0)\cap F\mathrm{\ne }\mathrm{\varnothing }$, which is exactly the condition $q_0\in F^{\mathrm{\prime }}$ from step 1.1. If $w\mathrm{\ne }\epsilon$, then step 2.1 and [L2] show that $N$ and $N^{\mathrm{\prime }}$ have the same reachable accepting states after reading $w$. Hence $L(N^{\mathrm{\prime }})=L(N)$.