The whole of the next page is an inductive proof of a theorem
that clearly implies the NDFA-to-DFA conversion algorithm
(repeated below for convenience) works. It's a bit of a bear to
follow along with, but let's try doing what we did often in
discrete: Look for the pieces we know must be present for a
valid inductive proof.
(i.e. closer to the base case) instances of
the statement we are trying to prove. On the next page, explain
how we know that, at the place you identified for (4), the
problem instance we are applying the inductive hypothesis to
has
Algorithm: NDFA-to-DFA Conversion
Input: a nondeterministic finite automaton
$M = \left(Q,\Sigma,\Delta,s,W\right)$, which has no
$\lambda$-transitions
Output: a deterministic finite automaton $M'$
such that $L(M') = L(M)$.
$
M' = \left( 2^{Q}, \Sigma, \delta, \{s\}, \{ R \in 2^{Q}\ |\ R
\cap Q \neq \emptyset \} \right)
$, where
$\delta(H,x) = \{ q \in Q \ |\ \exists p \in
H\left[(p,x,q) \in \Delta\right] \}$
If $M = (Q,\Sigma,\Delta,s,W)$ is an NDFA w/o
$\lambda$-transitions, and $M'$ is the DFA resulting from
the conversion algorithm, then for any string
$w = w_1\cdots w_n$, where each $w_i\in\Sigma$ we have:
$
(\{s\},w) \Rightarrow_{M'}^* (G,\lambda)
\text{ if and only if }
G = \{ q\in Q\ \big|\ (s,w) \Rightarrow_M^* (q,\lambda)\}.
$
Important: The way you want to read the conclusion of this
theorem is ...
$
\begin{array}{ccc}
\text{LHS} & & \text{RHS}\\
(\{s\},w) \Rightarrow_{M'}^* (G,\lambda) &
\text{ if and only if } &
G = \{ q\in Q\ \big|\ (s,w) \Rightarrow_M^* (q,\lambda)\}\\
{\small \begin{array}{l}
\text{from its start state, with $w$ as}\\[-.5em]
\text{input, $M'$ ends up in state $G$}\end{array}}
& &
{\small \begin{array}{l}
\text{$G$ consists of all states that are reachable}\\[-.5em]
\text{in $M$ starting from $s$ and reading $w$}\end{array}}
\end{array}
$
We proceed by induction on $n$, the length of $w$.
Case $n = 0$: In this case $w = \lambda$ and there is no
input to read. First consider LHS: In $M'$, the only configurations reachable in zero or more
steps from $(\{s\},\lambda)$ is $(\{s\},\lambda)$ itself.
So $G = \{s\}$ from LHS.
Next consider RHS: there is no input to read, and no lambda transitions in $M$, so
$
G = \{ q\in Q\ \big|\ (s,\lambda) \Rightarrow_M^*
(q,\lambda)\} = \{s\},
$
so $G = \{s\}$ on RHS. The theorem holds in this case.
Case $n > 0$: In this case $w = w'x$, where $w' \in \Sigma^*$ and
$x \in \Sigma$. In processing $w$, the last transition of
$M'$ looks like $(\cdot,x) \Rightarrow_{M'}
(\cdot,\lambda)$. So if we call the state we end up in
"$G$" and the state we were in when we started the last
transition $G'$ we get:
Analyze LHS ... focus on $M'$
1:
$
(\{s\},w) \Rightarrow_{M'}^* (G,\lambda) \text{ if and only if }
\underbrace{(\{s\},w') \Rightarrow_{M'}^*
(G',\lambda)}_{\text{call this (A)}}
\text{ and } \underbrace{G = \delta(G',x)}_{\text{call this (B)}}
$
2:
Applying induction to (A) gives: $(\{s\},w') \Rightarrow_{M'}^* (G',\lambda)$
if and only if
$G' = \{ q\in Q\ \big|\ (s,w') \Rightarrow_M^* (q,\lambda)\}$.
3:
Applying the definition of $\delta$ from the algorithm to
(B) gives:
$G = \{ q \in Q \ |\ \exists p \in G'\left[(p,x,q) \in \Delta\right] \}$
4:
Rewriting (1) using (2) and (3) gives:
$(\{s\},w) \Rightarrow_{M'}^* (G,\lambda) \text{ if and only if }
G' = \{ q\in Q\ \big|\ (s,w') \Rightarrow_M^* (q,\lambda)\}
\wedge
G = \{ q \in Q \ |\ \exists p \in G'\left[(p,x,q) \in \Delta\right] \}$
Analyze RHS ... focus on $M$
5:
For any state $q\in Q$:
$(s,w) \Rightarrow_M^* (q,\lambda)$
if and only if
$\exists p\in Q\left[(s,w'x) \Rightarrow_M^* (p,x) \Rightarrow_M (q,x)\right]$
if and only if
$\underbrace{\exists p\in Q\left[(s,w') \Rightarrow_M^* (p,\lambda)
\wedge (p,x,q) \in \Delta\right]}_{\text{call this (C)}}$
6:
The set of all $p\in Q$ that meet the first condition of
(C), i.e. $(s,w') \Rightarrow_M^* (p,\lambda)$, is exactly
the set we named "$G'$" in (2), so we can rewrite (C) as:
$\exists p\in G'\left[(p,x,q) \in \Delta\right]$
7:
Using (6) we can rewrite (5) as:
For any state $q\in Q$,
$(s,w) \Rightarrow_M^* (q,\lambda) \text{ if and only if }
\exists p\in G'\left[(p,x,q) \in \Delta\right]$.
Therefore,
$G = \{ q \in Q\ \big|\ (s,w) \Rightarrow_M^* (q,\lambda)\}
= \{ q \in Q\ \big|\ \exists p\in G'\left[(p,x,q) \in \Delta\right]\}$.
Point (4) tells us that LHS is equivalent to
$G = \{ q \in Q\ \big|\ \exists p\in G'\left[(p,x,q) \in \Delta\right]\}$.
Point (7) tells us that RHS is equivalent to
$G = \{ q \in Q\ \big|\ \exists p\in G'\left[(p,x,q) \in \Delta\right]\}$.
So, LHS $\Leftrightarrow$ RHS.
