I am reading through the first edition of $\textit{Introduction to Automata Theory, Languages, and Computation}$ by Hopcroft and Ullman.
They introduce the notions of NFA's and $\epsilon$-NFA's as follows.
Fix a finite alphabet $\Sigma$.
-
A $\Sigma$-NFA is a tuple $M = (Q,\delta, q_0, F)$ where $\delta: Q \times \Sigma^1 \rightarrow \mathbb{P}(Q)$ and $q_0 \in Q$.
We may extend $\delta$ to $\delta': Q \times \Sigma^{<\omega} \rightarrow \mathbb{P}(Q)$, by $\delta'(q,e) = \{q\}$ (where $e = \emptyset$ is the empty string) and for $w \in \Sigma^{<\omega}$ and $a \in \Sigma^{1}$, $\delta'(q,wa) = \bigcup_{r \in \delta'(q,w)} \delta(r,a)$. -
A $\Sigma$ – $\epsilon$ – NFA is a tuple $M = (Q, \alpha, q_0, F)$ where now $\alpha: Q \times (\Sigma \cup \{\epsilon\}) \rightarrow \mathbb{P}(Q)$ where $\epsilon$ is taken to be a symbol not in $\Sigma$.
Given $p \in Q$, we let $E(p)$ denote the $\epsilon$-closure, that is, all states $q \in P$ such that there is a transition path from $p$ to $q$ following only the symbol $\epsilon$. If $P \subseteq Q$, then let $E(P) = \bigcup_{p \in P} E(p)$.
Now $\alpha$ may be "extended" to $\beta: Q \times \Sigma^{<\omega} \rightarrow \mathbb{P}(Q)$ as follows: $\beta(q,e) = E(q)$, and $\beta(q,wa) = E\left(\bigcup_{r \in \beta(q,w)} \alpha(r,a)\right)$.
It is noted that this is not a true actual extension of $\alpha$.
Then they provide a proof (on page 26 and with different symbols) that given a $\Sigma$–$\epsilon$-NFA $M = (Q,\alpha, q_0, F)$ there is a $\Sigma$-NFA that accepts $L(M)$.
Let $N = (Q, \delta, q_0, G)$ where $$G = \begin{cases}F \cup \{q_0\}, & E(q_0) \cap F \neq \emptyset \\ F, & E(q_0) \cap F = \emptyset \end{cases}$$ and $\delta = \beta$ restricted to $Q \times \Sigma^{1}$ and extend it to $Q \times \Sigma^{< \omega}$ as before but it will just be called $\delta$ and not $\delta'$.
They claim that for all $q \in Q$ and $w \in \Sigma^{1}$ with $|w| \geq 1$, $\delta(q,w) = \beta(q,w)$, (actually just for $q_0$ but the argument doesn't seem to depend on $q_0$).
They prove this by induction on $|w|$.
For $w\in \Sigma^1$, $\delta(q,w) = \beta(q,w)$ by definition.
Now, assuming that $\delta(q,w) = \beta(q,w)$, and $a \in \Sigma^1$, then $$\delta(q,wa) = \bigcup_{r \in \delta(q,w)}\delta(r,a) = \bigcup_{r \in \beta(q,w)} \beta(r,a)$$ and $$\beta(q,wa) = E\left(\bigcup_{r \in \beta(q,w)} \alpha(r,a) \right)$$ so for these to be equal, we would need it to be true that $$E\left(\bigcup_{r \in \beta(q,w)} \alpha(r,a) \right) = \bigcup_{r \in \beta(q,w)} \beta(r,a)$$ and this is where I am unsure as to prove. It is simply stated to be true in the book.
So far I think it may be true that if $\{X_i\}_{i \in I}$ is a collection of sets then $E\left(\bigcup_{i \in I} X_i\right) = \bigcup_{i \in I} E(X_i)$, though I am suspicious of this due to the behavior of other closures in other fields.
If this is true, then $E\left(\bigcup_{r \in \beta(q,w)} \alpha(r,a) \right) = \bigcup_{r \in \beta(q,w)} E(\alpha(r,a))$, so it would suffice to show that for all $r \in \beta(q,w)$, $E(\alpha(r,a)) = \beta(r,a)$, but I have some doubts about this too.
Can anyone explain why $$E\left(\bigcup_{r \in \beta(q,w)} \alpha(r,a) \right) = \bigcup_{r \in \beta(q,w)} \beta(r,a)?$$ Thanks in advance for any assistance.
Best Answer
It's possible to see that $\beta(r,a) = E \left(\bigcup_{t \in \beta(r,\epsilon)} \alpha(t,a) \right) = E \left(\bigcup_{t \in E(r)} \alpha(t,a) \right) = E \left(\alpha'(E(r),a) \right)$, where $\alpha'(R,a) = \bigcup_{r \in R} \alpha(r,a)$. Thus, it follows from the definition of $E: Q \to \mathcal{P}(Q)$ that:
$$\bigcup_{r \in \beta(q,w)} \beta(r,a) = \bigcup_{r \in \beta(q,w)} E(\alpha'(E(r),a)) = E \left( \bigcup_{r \in \beta(q,w)} \alpha'(E(r),a) \right)$$
The last equality is possible because for a state $x$ to be in $\bigcup_{r \in \beta(q,w)} E(\alpha'(E(r),a))$, then it must be in the $\epsilon$-closure of some $\alpha'(E(r),a)$, $r \in \beta(q,w)$. We know $\alpha'(E(r),a) \in \left( \bigcup_{r \in \beta(q,w)} \alpha'(E(r),a) \right)$, and, therefore, we may conclude that $x$ is in the $\epsilon$-closure of the latter set, and that:
$$\left( \bigcup_{r \in \beta(q,w)} E(\alpha'(E(r),a)) \right) \subseteq E \left( \bigcup_{r \in \beta(q,w)} \alpha'(E(r),a) \right)$$
The other direction follows similarly. With this we can arrive at your desired equality:
$$E \left( \bigcup_{r \in \beta(q,w)} \alpha'(E(r),a) \right) = E \left( \bigcup_{r \in \beta(q,w)} \alpha(r,a) \right)$$
That's so because there isn't any state $r \in \beta(q,w)$ such that there is a path of $\epsilon$-transitions from it to another state not already in $\beta(q,w)$.