# 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\)