(related to Theorem: Reduction of NFA to DFA (Rabin-Scott Theorem))

We will prove the theorem by showing the set equality $\mathcal L(\operatorname{NFA})=\mathcal L(\operatorname{DFA}).$

- The definition of the deterministic finite automaton. DFA is a special case of the definition of the non-deterministic finite automaton. NFA.
- This is because in a given DFA definition $A=(C,\Sigma,\delta,F,s_0),$ we just have to replace $s_0$ by the set $S=\{s_0\}$ and the function $\delta$ is a special case of a relation $\Delta$ (in fact, every function is a left-total, right-unique relation.
- With these replacements, we have $A=(C,\Sigma,\Delta,F,S)$ as a special case of an NFA.

just to replace the function definition by the other by replacing the function `$\d

- Let $A=(C,\Sigma,\Delta,F,s_0)$ be an NFA.
- We construct a DFA $A^\prime=(C^\prime,\Sigma,\delta,F^\prime,s_0^\prime)$ by making the following replacements:
- We replace the set of states $C$ of the NFA by the power set of $C$, i.e. $$C^\prime:=\mathcal P( C).$$ Note that the power set has also finitely many elements, just like $C$ has.
- We set the starting state of the DFA to $$s_0^\prime:=\{s_0\}\in C^\prime$$ (the singleton containing the starting state of the NFA).
- Note that if for a string $\sigma_0,\sigma_1,\ldots,\sigma_n\in\Sigma^*$ the NFA is in a state $q$, this means by the definition of $L(\operatorname{NFA})$ that there is a starting state $s_0\in S$ with $q=\Delta(\ldots\Delta(\Delta(s_0,\sigma_0),\sigma_1),\ldots,\sigma_n)\in F$.
- We define for all words $\sigma_0,\sigma_1,\ldots,\sigma_n\in\Sigma^*$ and all states $Q\in C^\prime$ the function $\delta:(C^\prime\times \Sigma^*)\to C^\prime$ by $$\delta(\ldots\delta(\delta(s_0,\sigma_0),\sigma_1),\ldots,\sigma_n)=Q\in C^\prime\Longleftrightarrow \exists s_0\in S,\; \Delta(\ldots\Delta(\Delta(\{s_0\},\sigma_0),\sigma_1),\ldots,\sigma_n)=q\in Q\subseteq C$$
- This means, we define the DFA to be exactly in the state $Q\in C^\prime,$ if and only if for the same word the corresponding NFA produces one of the states $q\in Q\subseteq C.$
- The final states $F^\prime$ will be defined by all $Q\in C^\prime$ containing at least one final state $q\in F$, in other words, $$F^\prime:=\{Q\in C^\prime\mid Q\cap F\neq\emptyset\}.$$

- It follows by construction, that $A^\prime$ is a DFA accepting exactly the same words as the given NFA.∎

**Erk, Katrin; Priese, Lutz**: "Theoretische Informatik", Springer Verlag, 2000, 2nd Edition**Hoffmann, Dirk**: "Theoretische Informatik, 3. Auflage", Hanser, 2015