Epsilon Non Deterministic Finite Automata proof

Question

1. 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.

Answer 1

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^*\ . $$