Epsilon Non Deterministic Finite Automata proof 
*

*Let M = (Q, Σ, δ, q0, A) be an ε-NFA and let S ⊆ Q. Prove that ε(S) =
ε(ε(S)).


I will provide some definitions that may be useful in answering the question
Formal Definition of ε-NFA M = (Q, Σ, δ, q0, A)
with the difference from an NFA in that δ : Q × (Σ ∪ {ε}) → 2^
Q
L(M) = {x ∈ Σ
*
: δ
*
(q0, x) ∩ A ≠ ∅} this is the same definition of L(M) as
per the NFA.
This means that we must consider the ε moves somewhere. And we do this
in the extended transition function.
First we define the ε-closure : ε : 2^Q → 2^
Q
It is defined as follows
1) S ⊆ ε(S)
2) if q ∈ ε(S) then δ(q, ε) ⊆ ε(S)
3) and nothing else is in ε(S)
I have tried answering this but am stuck and could use an explanation.
 A: This is a "short" answer (made long only by building propositions), which is based on a slightly more exact definition of $\epsilon(S)$. This is:
$\epsilon(S)$ is the minimal under the possible sets $T$ of states with the properties:


*

*(1) $T$ contains $S$, and

*(2) starting from $q\in T$ and reading $\epsilon$ we also land in $T$.


Moreover, a state $r^*$ is in $\epsilon(S)$, iff 


*

*(3) $r^*$ can be constructed using a chain with $r_0\in S$
$$
r_0\overset\epsilon\to
r_1\overset\epsilon\to
r_2\overset\epsilon\to
\dots
\overset\epsilon\to
r_N=r^*\ ,
$$
where $N$ is a suitable number of steps. (In fact, all steps in between are
also in $\epsilon(S)$, but we do not require this, since applying this would mean to show more.) 


The notation $q\overset\epsilon\to r$ is a short cut for $r\in\delta(q,\epsilon)$. In words, we land from $q$ in $r$ by eating $\epsilon$ in a step. Taking $\epsilon(S)$ means taking the "completion" of this relation, and then by considering the equivalence classes of all elements in $S$. (We are "starting in $S$" and eating $\epsilon$ (nothing) on zero, one, or more steps successively, starting again from the previous landing point. We need the obvious transitivity of this completion below.)
Now we show the wanted equality by double inclusion.

We show $\epsilon(S) \subseteq \epsilon(\epsilon(S))$. This is clear from the property (1) applied for $S'=\epsilon(S)$ (instead of $S$).
We show $\epsilon(S) \supseteq \epsilon(\epsilon(S))$. We start with a state $r^*$ in $\epsilon(\epsilon(S))$. (And want to show it is in the set on the L.H.S. .)
Then this state can be reached by "reading $\epsilon$" in a chain:
$$
r'_0\overset\epsilon\to
r'_1\overset\epsilon\to
r'_2\overset\epsilon\to
\dots
\overset\epsilon\to
r'_N=r^*\ ,
$$
where $r'_0\in\epsilon(S)$. Since $r'_0\in \epsilon(S)$, we can build a chain from some $s_0\in S$ to $r'_0$. And we are done when writing: 
$$
s_0\overset\epsilon\to s_1\overset\epsilon\to s_2\overset\epsilon\to\dots
\overset\epsilon\to s_M=
r'_0\overset\epsilon\to
r'_1\overset\epsilon\to
r'_2\overset\epsilon\to
\dots
\overset\epsilon\to
r'_N=r^*\ .
$$
