# Lecture 7: Non-deterministic vs Deterministic Finite Automata

The following theorem shows that deterministic and non-deterministic finite automata accept the same class of languages.

Theorem: For every non-deterministic finite automaton $N$, there exists a deterministic finite automaton $M$ that accepts the same language, $L(M)=L(N)$.

Proof: The idea is to have states in $M$ that correspond to subsets of states in $N$. Let $Q_N$ be the states of $N$. We want that for every word $w\in\Sigma^\ast$, the automaton $M$ is in the following state after reading $w$, $\delta_M^\ast(w) = \{ q\in Q_N \mid \text{N has a computation path for the word w that ends in the state q} \}.$ If we have an automaton $M$ with this property, then it has the same language as $N$ if we choose the accept states of $M$ as $F_M = \{ Q \subseteq Q_N \mid \text{Q contains an accept state of N} \}.$ Let $q_0$ be the start state of $N$. As start state for $M$, we choose $Q_0=\{ q\in Q_N \mid \text{q can be reached from q_0 by \varepsilon-transitions} \}.$ Finally, the transition function of $M$ is defined as \begin{aligned} \delta_M(Q,x) = \{q\in Q_N\mid &\text{q can be reached from a state in Q by \varepsilon-transitions }\\ \qquad \qquad \qquad&\text{and exactly one x-transition} \}. \end{aligned} With this transition function and start state, the repeated transition function $\delta_M^\ast$ indeed has the property above (proof by induction). Therefore, \begin{aligned} w \in L(M) \Leftrightarrow& \delta_M^\ast(w)\in F_M\\ \Leftrightarrow & \text{N has a computation for w that ends in an accept state of N}\\ \Leftrightarrow & w\in L(N). \end{aligned} $\square$