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

- $$Q^\prime = P(Q)$$
- $$δ^\prime(R, a) = \bigcup_{q\in R} E(δ(q,a)) $$
- $$q_0^\prime = E(\{q_0\})$$
- $$F^\prime = \{R \in Q^\prime | R \text{ contains an accept state of } N\}$$