Theorem 1.0.0

Every nondeterministic finite automaton has an equivalent deterministic finite automaton.


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