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$$.