# Let M be an $\epsilon$-NFA and let $S\subseteq Q$. Prove $\epsilon (S) = \epsilon (\epsilon (S))$

Let M be an $$\epsilon$$-NFA and let $$S\subseteq Q$$. Prove $$\epsilon (S)= \epsilon (\epsilon (S))$$.

I would like to prove this by contradiction but I don't know if my idea is correct.

Definition of $$\epsilon -closure$$: $$\epsilon : 2^Q \rightarrow 2^Q$$

a) $$S \subseteq \epsilon (S)$$ Base case

b) If $$q \in \epsilon (S)$$ then $$\delta(q,\epsilon )\subseteq \epsilon (S)$$ Recursive case

c) and nothing else is in $$\epsilon (S)$$

Prove i) That $$\epsilon (S) \subseteq \epsilon (\epsilon (S))$$.

By contradiction, suppose $$\exists x \in \epsilon (S)$$ such that $$x \notin \epsilon (\epsilon (S))$$.

Using definitions of $$\epsilon (S)$$ , we know $$S \in \epsilon (S)$$. So $$x \in S \in \epsilon (S)$$, and $$\delta(x,\epsilon ) \subseteq \epsilon (S)$$.

Using definitions again, we know $$S \in \epsilon (S)$$, so $$x \notin \epsilon (\epsilon (S))\notin \epsilon (S)$$. Also $$\delta (x, \epsilon) \nsubseteq \epsilon (\epsilon (S))$$

We have a contradiction because $$x \notin \epsilon (S)$$ and we said $$x \in \epsilon (S)$$.

Therefore i) is true.

• Oct 16 '19 at 17:50

Your definition of $$\epsilon$$-closure is quite problematic. Here is a better formulation:

$$\epsilon(S)$$ is the intersection of all sets $$T \subseteq Q$$ such that (i) $$T \supseteq S$$ and (ii) if $$q \in T$$ then $$\delta(q,\epsilon) \subseteq T$$.

Here is a series of claims which imply $$\epsilon(S) = \epsilon(\epsilon(S))$$.

Claim 1. $$\epsilon(S) \supseteq S$$.

Proof. $$\epsilon(S)$$ is the intersection of sets containing $$S$$, and so contains $$S$$.

Claim 2. If $$q \in \epsilon(S)$$ then $$\delta(q,\epsilon) \subseteq \epsilon(S)$$.

Proof. If $$q \in \epsilon(S)$$ then $$q$$ belongs to all sets $$T$$ in the definition. Property (ii) implies that all of these sets contain $$\delta(q,\epsilon)$$, and so $$\epsilon(S)$$ contains $$\delta(q,\epsilon)$$.

Claim 3. $$\epsilon(\epsilon(S)) \supseteq \epsilon(S)$$.

Proof. Follows directly from Claim 1.

Claim 4. $$\epsilon(\epsilon(S)) \subseteq \epsilon(S)$$.

Proof. $$\epsilon(S)$$ satisfies the $$T$$-conditions for $$\epsilon(S)$$: (i) is trivial, and (ii) follows from Claim 2.

Claim 5. $$\epsilon(\epsilon(S)) = \epsilon(S)$$.

Proof. Follows from Claim 3 and Claim 4.

• I don't really know how to put into words that $\epsilon (\epsilon (S)) \subseteq \epsilon (S)$. Is saying "Since $S \subseteq \epsilon (S)$ then $\epsilon (\epsilon (S)) \subseteq \epsilon (S)$ enough? Oct 14 '19 at 21:49
• It's not convincing. What I wrote is just a sketch, which needs expansion. Oct 14 '19 at 21:51