# Proof

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

just to replace the function definition by the other by replacing the function `$\d ###$\mathcal L(\operatorname{DFA}) "\supseteq" \mathcal L(\operatorname{NFA})$• 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.

Thank you to the contributors under CC BY-SA 4.0!

Github:

### References

#### Bibliography

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