1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Mandy Oct 14 '19 at 21:49
  • $\begingroup$ It's not convincing. What I wrote is just a sketch, which needs expansion. $\endgroup$ – Yuval Filmus Oct 14 '19 at 21:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.