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

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?

• Could you please give the definition of Ɛ(S) ? – J.-E. Pin Oct 16 '19 at 4:17
• Ɛ(S) is the same as eclosure(S), just saying we are taking the epsilon closure on the set S ⊆ Q – Ryan Gomez Oct 16 '19 at 16:22
• Sorry to insist, but this is still not precise enough. Is Ɛ(S) the set of states $q$ such that there exists an Ɛ-path from some state of $S$ to $q$, or the the set of states $q$ such that there exists an Ɛ-path from $q$ to some state of $S$? By the way, giving a precise definition is an important step towards the answer to your question. – J.-E. Pin Oct 16 '19 at 16:31
• No worries, it is the the set of states q such that there exists an Ɛ-path from q to some state of S – Ryan Gomez Oct 16 '19 at 16:42
• How would you go about doing it with the other definition? Using the set of states q such that there exists an Ɛ-path from some state of S to q? I may have been confused on the definitions for the question. – Ryan Gomez Oct 16 '19 at 17:11

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.