Finite-Automata Transition and Determinisation Interfaces

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.

Since $Q$ is finite, $\mathcal{P}(Q)$ is finite with $2^{\mathrm{\mid }Q\mathrm{\mid }}$ elements. It is nonempty because $\mathrm{\varnothing }\subseteq Q$. For every $T\subseteq Q$ and $a\in \mathrm{\Sigma }$, all $\delta (q,a)$ lie in $\mathcal{P}(Q)$, so their union and its closure are subsets of $Q$. Thus $\mu$ is defined on all $\mathcal{P}(Q)\times \mathrm{\Sigma }$ and takes values in $\mathcal{P}(Q)$. Moreover $S_0\subseteq Q$ and $G\subseteq \mathcal{P}(Q)$. These verify the DFA hypotheses and give its extended transition ${\mu }^{\ast }$.

Fix any $S\subseteq Q$. At length zero, ${\mu }^{\ast }(E(S),\epsilon )=E(S)=\widehat{\delta }(S,\epsilon )$. This includes $S=\mathrm{\varnothing }$ and subsets that are not epsilon-closed.

Assume the equality holds for every word $u$ of length $k$, and write a word of length $k+1$ uniquely as $ua$. Then ${\mu }^{\ast }(E(S),ua)=\mu ({\mu }^{\ast }(E(S),u),a)=\mu (\widehat{\delta }(S,u),a)=E({\bigcup }_{q\in \widehat{\delta }(S,u)}\delta (q,a))=\widehat{\delta }(S,ua)$. The second equality uses the induction hypothesis, and the last uses the NFA recursion.

Induction on length proves the equality for every $w$; since $S$ was arbitrary, it holds for every subset. Taking $S=\{q_0\}$ gives ${\mu }^{\ast }(S_0,w)=\widehat{\delta }(q_0,w)$.

If $D_N$ accepts $w$, then ${\mu }^{\ast }(S_0,w)\in G$, so $\widehat{\delta }(q_0,w)\cap F\mathrm{\ne }\mathrm{\varnothing }$ and $N$ accepts $w$. Conversely if $N$ accepts $w$, that intersection is nonempty, so ${\mu }^{\ast }(S_0,w)\in G$ and $D_N$ accepts $w$. This proves equality of the two languages, also for $F=\mathrm{\varnothing }$ (neither accepts) and $F=Q$ (acceptance is exactly nonemptiness of the reached subset).

For any letter $a$, the union indexed by the empty set is empty, whence $\mu (\mathrm{\varnothing },a)=E(\mathrm{\varnothing })=\mathrm{\varnothing }$. Its extended transition stays empty: the empty-word value is empty, and if the value at $u$ is empty, the successor value is $\mu (\mathrm{\varnothing },a)=\mathrm{\varnothing }$. Induction gives absorption for every word. If $\mathrm{\Sigma }=\mathrm{\varnothing }$, the transition has empty domain and the same empty-word calculation applies; a one-state $Q$ causes no exception to the power-set count or the proof.

For each letter pair $(q,a)$ the element $d(q,a)$ exists in $Q$, so its singleton is a subset of $Q$. Each epsilon value is also a subset of $Q$, and the tagged epsilon domain is disjoint from the letter domain. Thus the prescription is total into $\mathcal{P}(Q)$; the other tuple requirements are inherited from $D$. It defines $N_D$.

For any $S\subseteq Q$, the first saturation stage is $S\cup {\bigcup }_{q\in S}\mathrm{\varnothing }=S$. Whenever a stage equals $S$, its next stage has the same value. Induction gives $C_k(S)=S$ for all $k$, hence $E(S)=S$, including $S=\mathrm{\varnothing }$.

Fix $q\in Q$. For the empty word, $\widehat{\delta }(q,\epsilon )=E(\{q\})=\{q\}=\{d^{\ast }(q,\epsilon )\}$.

Assume $\widehat{\delta }(q,u)=\{d^{\ast }(q,u)\}$ for all words of length $k$. For a word $ua$ of length $k+1$, the union defining its next NFA state set has the single index $d^{\ast }(q,u)$. Therefore $\widehat{\delta }(q,ua)=E(\delta (d^{\ast }(q,u),a))=E(\{d(d^{\ast }(q,u),a)\})=\{d^{\ast }(q,ua)\}$. These equalities use the displayed singleton prescription, the identity closure, and the DFA successor equation.

Induction proves the singleton identity for every word and every initial state $q$. This remains valid when the alphabet is empty, since then there is only the empty word, and when $Q$ has one state.

At $q=q_0$, nonempty intersection $\widehat{\delta }(q_0,w)\cap F\mathrm{\ne }\mathrm{\varnothing }$ implies its sole possible element $d^{\ast }(q_0,w)$ lies in $F$. Conversely membership of that element in $F$ witnesses the nonempty intersection. The NFA and DFA acceptance tests therefore agree for every word, giving $L(N_D)=L(D)$; in particular empty $F$ rejects all words and $F=Q$ accepts all words.