Theorem 1.0.0

Every nondeterministic finite automaton has an equivalent deterministic finite automaton.

$PROOF:$

Let $N = (Q, Σ, δ, q_0, F)$ be NFA recognising some language $A$. We will construct a DFA $M = (Q^\prime, Σ, δ^\prime, q_0^\prime, F^\prime)$ recognising $A$.

1. $Q^\prime = P(Q)$
2. $δ^\prime(R, a) = \bigcup_{q\in R} E(δ(q,a))$
3. $q_0^\prime = E(\{q_0\})$
4. $F^\prime = \{R \in Q^\prime | R \text{ contains an accept state of } N\}$
We have now completed the construction of the DFA $M$ that simulates the ε-NFA $N$.