Prove that Ɛ(S) = Ɛ(Ɛ(S))

Question

Let M = (Q, Σ, δ, q0, A) be an Ɛ-NFA and let S ⊆ Q

I am having problems starting this question. Would it be reasonable to find a proof for Ɛ(S) = S, and then proving Ɛ(S) = Ɛ(Ɛ(S))? If not, how would you go about doing this proof?

Answer 1

I would have taken the other definition, but let us work with your definition. First of all, $Ɛ(S)$ is not necessarily equal to $S$. Take for instance a two-state automaton containing only one Ɛ-transition, namely $$ 0 \xrightarrow{Ɛ} 1 $$ and let $S = \{1\}$. Then $Ɛ(S) = \{0, 1\}$ since there exists an $Ɛ$-path from $0$ to $1$ and also $Ɛ$-path from $1$ to $1$ (the empty path).

You should be able to prove that $Ɛ(Ɛ(S)) = Ɛ(S)$. Hint: the composition of two Ɛ-paths is an Ɛ-path.