Correctness of the Subset Construction

Statement

Theorem: Let $M$ be an NFA-$\varepsilon$ and $\mathcal{P}(M)$ the result of subset construction. Then $L(M) = L(\mathcal{P}(M))$.

We prove two directions:

1. Soundness: $L(\mathcal{P}(M)) \subseteq L(M)$
2. Completeness: $L(M) \subseteq L(\mathcal{P}(M))$

Examinable Proof: Soundness

Claim: If $\mathcal{P}(M)$ accepts $w$, then $M$ accepts $w$.

Proof:

Suppose $\mathcal{P}(M)$ accepts $w = a_1 a_2 \cdots a_n$.

There is a DFA computation:

$s' \xrightarrow{a_1} S_1 \xrightarrow{a_2} \cdots \xrightarrow{a_n} S_n$

where $S_n \cap F \neq \emptyset$.

Build an NFA computation:

We show by induction on $i$ that for each $S_i$, and for each $q \in S_i$, there is an NFA path from $s$ to $q$ on input $a_1 \cdots a_i$.

Base ($i = 0$): $s' = E(s)$. Every $q \in s'$ is reachable from $s$ via $\varepsilon^*$.

Step: Suppose for each $q' \in S_{i-1}$, there is an NFA path $s \Rightarrow a_1 \cdots a_{i-1} q'$.

For $q \in S_i$: By construction, $q \in \delta'(S_{i-1}, a_i)$.

So there exists $q' \in S_{i-1}$ with $q' \xrightarrow{a_i} q'' \xrightarrow{\varepsilon^*} q$ for some $q''$.

By IH, $s \Rightarrow a_1 \cdots a_{i-1} q'$. Thus $s \Rightarrow a_1 \cdots a_i q$.

Conclusion: Since $S_n \cap F \neq \emptyset$, there exists $q_f \in F \cap S_n$ reachable from $s$ via $w$. Hence $M$ accepts $w$.

Examinable Proof: Completeness

Claim: If $M$ accepts $w$, then $\mathcal{P}(M)$ accepts $w$.

Proof:

Suppose $M$ accepts $w = a_1 \cdots a_n$.

There exists an NFA computation:

$s = q_0 \xrightarrow{a_1} q_1 \xrightarrow{a_2} \cdots \xrightarrow{a_n} q_n \in F$

(where each step may involve $\varepsilon$-transitions).

Build the DFA computation:

Define DFA states $S_0, S_1, \ldots, S_n$ where $S_i =$ the set of NFA states reachable from $s$ on input $a_1 \cdots a_i$ via any path.

Formally: $S_i = \delta'(S_{i-1}, a_i)$ with $S_0 = E(s) = s'$.

Key lemma: By construction, $q_i \in S_i$ for all $i$.

Proof of lemma: By induction on $i$.

• $q_0 \in E(s) = S_0$ (by definition of NFA computation starting at $s$).
• If $q_{i-1} \in S_{i-1}$ and $q_{i-1} \xrightarrow{a_i} q_i$, then $q_i \in \delta'(S_{i-1}, a_i) = S_i$.

Conclusion: $q_n \in S_n$. Since $q_n \in F$, we have $S_n \cap F \neq \emptyset$. Thus $\mathcal{P}(M)$ accepts $w$.

Equivalence of NFA, NFA-$\varepsilon$, and DFA

Corollary

$(\text{NFA languages}) = (\text{NFA-}\varepsilon\text{ languages}) = (\text{DFA languages})$

All three formalisms recognise exactly the same class of languages: the regular languages.

Proof

• NFA subset of NFA-$\varepsilon$: trivial (NFA is NFA-$\varepsilon$ with empty $\tau$)
• NFA-$\varepsilon$ subset of DFA: subset construction (theorem above)
• DFA subset of NFA: trivial (DFA is special case of NFA)

---

Summary

• Soundness: DFA path gives NFA path by tracking which NFA states are reachable
• Completeness: NFA path traced through DFA by tracking sets
• All three automata types (NFA, NFA-$\varepsilon$, DFA) recognise the same languages