Epsilon-NFAs, finite epsilon closure, and extended word transition

For $T\subseteq Q$, the union of the sets $\delta (q,\epsilon )$ with $q\in T$ is a subset of $Q$. Thus $H(T)=T\cup {\bigcup }_{q\in T}\delta (q,\epsilon )$ is a self-map of $\mathcal{P}(Q)$. Applying natural-number recursion with initial element $S$ gives the unique sequence $C_k(S)$, with $C_k(S)\subseteq C_{k+1}(S)\subseteq Q$.

If $C_j=C_{j+1}$, applying $H$ repeatedly gives $C_{j+r}=C_j$ for every natural $r$: the case $r=0$ is equality and the successor follows from $H(C_j)=C_j$. If $C_n\mathrm{\ne }{C}_{n+1}$, therefore all inclusions from $C_0$ through $C_{n+1}$ are strict. Each raises natural cardinality by at least one, by the finite-subset equality criterion. Starting at $\mathrm{\mid }{C}_0\mathrm{\mid }\ge 0$, induction gives $\mathrm{\mid }{C}_{n+1}\mathrm{\mid }\ge n+1$, contradicting $C_{n+1}\subseteq Q$ and $\mathrm{\mid }Q\mathrm{\mid }=n$. Hence $C_n=C_{n+1}$ and all subsequent stages equal $E(S)$.

The equality $H(E(S))=E(S)$ says precisely that $E(S)$ is epsilon-closed, and $S=C_0\subseteq E(S)$. If $S\subseteq T$ and $T$ is epsilon-closed, then $C_0\subseteq T$; from $C_k\subseteq T$, every successor of a state in $C_k$ is in $T$, so $C_{k+1}\subseteq T$. Induction gives $E(S)\subseteq T$. This proves leastness and extensivity.

For every $k$, $C_k(S)$ is exactly the set of endpoints of epsilon paths from $S$ with at most $k$ edges. At $k=0$ both sets are $S$. An endpoint in $C_{k+1}$ either already lies in $C_k$, or follows one epsilon edge from a state in $C_k$; retaining or appending that edge gives a path of length at most $k+1$. Conversely a path of length at most $k+1$ either has length zero, or deleting its last edge leaves a path of length at most $k$, whose endpoint belongs to $C_k$; its last endpoint lies in $C_{k+1}$. These implications give the successor equivalence and induction proves the claim. Stabilization then implies that $E(S)$ is exactly the endpoints of all finite epsilon paths: paths of length at most $n$ give $C_n$, while longer paths give a stage equal to $C_n$.

If $S\subseteq T$, the closed set $E(T)$ contains $S$, so leastness gives $E(S)\subseteq E(T)$. Because $E(S)$ is already closed, leastness gives $E(E(S))\subseteq E(S)$ and extensivity gives the reverse inclusion. For any family $(S_i{)}_{i\in I}$, a path starts in ${\bigcup }_i{S}_i$ exactly when its starting state belongs to some $S_i$. Applying the endpoint equivalence gives $E({\bigcup }_i{S}_i)={\bigcup }_{i}E(S_i)$ in both directions. For $I=\mathrm{\varnothing }$ neither side has a path starting point, so $E(\mathrm{\varnothing })=\mathrm{\varnothing }$.

Fix $w:r\to \mathrm{\Sigma }$. On $\mathbb{N}\times \mathcal{P}(Q)$ define $J_w(i,T)=(i+1,E({\bigcup }_{q\in T}\delta (q,w(i))))$ if $i<r$, and $J_w(i,T)=(i,T)$ if $i\ge r$. In the first clause $w(i)$ exists; in both clauses the value lies in the product. Recursion starting at $(0,E(S))$ gives a unique sequence. For $k\le r$ its value is $(k,T_k)$, as follows by induction from its first clause. In particular $T_0=E(S)$ and $T_{k+1}=E({\bigcup }_{q\in T_k}\delta (q,w(k)))$ for $k<r$. Define $\widehat{\delta }(S,w)=T_r$. The graph is the subset of $(\mathcal{P}(Q)\times {\mathrm{\Sigma }}^{\ast })\times \mathcal{P}(Q)$ consisting of the triples satisfying this finite-sequence prescription, so Separation gives a set function; existence and uniqueness of the sequence give exactly one output for each input. Here the ambient products are sets; the finite-sequence condition is a set-theoretic formula with parameters $S,w,\delta$.

If two words agree at positions below $m$, their sequences for the same $S$ agree through stage $m$: the initial sets agree, and equality at stage $k<m$ gives equal unions with the same letter, hence equal next closures. Induction proves this prefix compatibility. Taking the words $u$ and $ua$ proves the displayed successor equation, while $r=0$ proves the empty-word equation. Any other function satisfying those equations agrees at the empty word and, if it agrees at $u$, agrees at $ua$ by substitution. Every nonempty word has this last-letter decomposition, so induction on length proves uniqueness on all words.

For spelling $\epsilon$, the endpoint assertion is the epsilon-path assertion. Suppose the assertion holds for $u$ and consider $ua$. A path spelling $ua$ has a last non-epsilon edge: its label is $a$, its preceding path spells $u$, and its following path has only epsilon labels. The preceding endpoint is in $\widehat{\delta }(S,u)$, so the last edge lands in ${\bigcup }_{q\in \widehat{\delta }(S,u)}\delta (q,a)$ and its epsilon suffix lands in the closure of that union. Conversely a state in this closure has an epsilon path from some $v\in \delta (q,a)$ with $q\in \widehat{\delta }(S,u)$. The induction hypothesis supplies a path spelling $u$ to $q$; concatenating this path, the edge to $v$, and that epsilon path gives spelling $ua$. Only witnesses for this one membership are used. Induction proves both directions for all words.

Consequently the acceptance predicate holds exactly when a finite path from $q_0$ spelling $w$ ends in $F$. Its defining set is a subset of ${\mathrm{\Sigma }}^{\ast }$, hence a language. Empty $S$ has no path starts, so $\widehat{\delta }(\mathrm{\varnothing },w)=\mathrm{\varnothing }$ for every word; empty $F$ accepts no word. If $\mathrm{\Sigma }=\mathrm{\varnothing }$ the only word is $\epsilon$, already treated. A one-state $Q$ and epsilon self-loops satisfy the same stabilization argument; $Q=\mathrm{\varnothing }$ is excluded by $q_0\in Q$. Thus the definitions and all asserted properties are well-defined in the boundary cases as well.